高一數(shù)學(xué)競(jìng)賽講義第1~7講

高一數(shù)學(xué)競(jìng)賽講義

目錄

1.第一講組合計(jì)數(shù)（1）.......................................................2

1.1.本講概述................................................................2

1.1.1,加法原理與乘法原理.................................................3

1.1.2.無重排列與組合.....................................................3

1.1.3.可重排列與組合（僅給出結(jié)論，請(qǐng)自證之）...........................3

1.1.4.圓排列（僅給出結(jié)論，請(qǐng)自證之）....................................4

1.2,例題精講.................................................................4

1.2.1.板塊一利用加法、乘法原理以及枚舉方法計(jì)數(shù).........................4

1.2.2.板塊二映射與對(duì)應(yīng)方法..............................................9

2.第二講組合計(jì)數(shù)（2）........................................................15

2.1.本講概述................................................................15

2.2.例題精講..............................................................15

2.2.1.板塊一算兩次....................................................15

2.2.2.板塊二遞推方法................................................18

2.2.3.板塊三組合計(jì)數(shù)綜合問題...........................................19

3.第三講二項(xiàng)式定理與組合恒等式..............................................25

3.1.本講概述..............................................................25

3.2.例題精講..............................................................26

4.第四講抽屜原理與存在性問題................................................34

4.1.本講概述...............................................................34

4.2.例題精講..............................................................35

5.第五講容斥原理與極端性原理................................................45

5.1.本講概述..............................................................45

5.2.例題精講..............................................................46

5.2.1.板塊一容斥原理..................................................46

5.2.2.板塊二極端性原理...............................................50

6.第六講染色問題與操作問題..................................................55

6.1.本講概述...............................................................55

6.2.例題精講..............................................................55

6.2.1.板塊一染色問題..................................................55

6.2.2.板塊二操作問題................................................59

第1頁(yè)共82頁(yè)

7.第七講組合綜合問題.........................................................64

7.1.本講概述................................................................64

7.2.例題精講................................................................64

1.第一講組合計(jì)數(shù)（1）

1.1.本講概述

組合數(shù)學(xué)是競(jìng)賽中最重要的一個(gè)板塊，也是變化最多，最靈活，難以掌握,

至今還沒有一個(gè)系統(tǒng)體系的學(xué)科.解決競(jìng)賽中的組合數(shù)學(xué)問題，往往不需要太多

專門的知識(shí)，而是要求深刻的洞察能力和強(qiáng)大的化歸、轉(zhuǎn)化能力.所謂”得組合

者得天下”，在聯(lián)賽一二試乃至冬令營(yíng)、集訓(xùn)隊(duì)、IMO中，最后的勝者往往是

成功完成組合問題的同學(xué).因此，學(xué)習(xí)組合數(shù)學(xué)對(duì)于競(jìng)賽獲獎(jiǎng)以及數(shù)學(xué)能力的培

養(yǎng)都有著十分重要的意義.

從本講開始，我們將用七講來對(duì)組合數(shù)學(xué)做一個(gè)大致的勾勒.通過這七講的

學(xué)習(xí)，達(dá)到以下目的：1、掌握聯(lián)賽一二試組合問題的特點(diǎn)與解法；2、對(duì)組合

數(shù)學(xué)這門學(xué)科有一個(gè)初步的認(rèn)識(shí)，為進(jìn)一步學(xué)習(xí)打下基礎(chǔ)；3、了解部分冬令營(yíng)

級(jí)別組合問題的難度與解題模式.

七講內(nèi)容分別為：

一、組合計(jì)數(shù)（1）比高考略難的基本計(jì)數(shù)問題

二、組合計(jì)數(shù)（2）需要較多技巧的專門計(jì)數(shù)問題

三、組合恒等式較為重要和有趣味的組合恒等式

四、抽屜原理與存在性問題

五、容斥原理與極端性原理

六、染色問題與操作問題

七、組合數(shù)學(xué)綜合問題

本講中，假定各位同學(xué)已經(jīng)大致學(xué)完了高考難度的排列組合模塊內(nèi)容，對(duì)加

法原理、乘法原理等有一定的理解并能完成相關(guān)的問題.

教師備注：本講可與下一講打通講述，也可本講專門講常規(guī)的枚舉、基本的

組合問題，下一講專門講述一些較為高級(jí)的技巧.

首先給出一些相關(guān)的基本知識(shí)：

第2頁(yè)共82頁(yè)

1.1.1.加法原理與乘法原理

加法原理：完成一件事的方法可分成n個(gè)互不相交的類，在第1類到第n

類分別有叫,，々，…,"J種方法，則總共完成這件事有=町+m2+...+mn種

/=I

方法.

應(yīng)用加法原理的關(guān)鍵在于通過適當(dāng)?shù)姆诸?，使得每一類都相?duì)易于計(jì)數(shù).

乘法原理：完成一件事的方法有n個(gè)步驟，，在第1步到第n步分別有

班,網(wǎng),...,加“種方法，則總共完成這件事有j?叫=，"]?機(jī)種方法?應(yīng)用乘法

/=I

原理的關(guān)鍵在于通過適當(dāng)?shù)姆植?，使得每一步都相?duì)易于計(jì)數(shù).

由上可見，加法原理與乘法原理也是化歸思想的應(yīng)用，通過這兩個(gè)原理以及

它們的組合，可以將一個(gè)復(fù)雜的組合計(jì)數(shù)問題分解成若干個(gè)便于計(jì)數(shù)的小問題.

1.1.2.無重排列與組合

階乘:定義n!=n?(n-l)?(n-2)?...?2?l,讀作n的階乘

無重排列：從n個(gè)不同元素中任取m個(gè)不同元素排成一列，不同的排列種

數(shù)稱為排列數(shù)，記為(部分書中記為尸"),由乘法原理得到

M=---------=〃?(〃-D〃一機(jī)+1)

(n-fn)!

無重組合：從n個(gè)不同元素中任取m個(gè)元素并為一組，不同的組合種數(shù)稱

為組合數(shù)，記為C其公式為

CY="PT”…?("f+D=―d_

“mlm?(n-ni)??m?

1.1.3.可重排列與組合(僅給出結(jié)論，請(qǐng)自證之)

可重排列：從n個(gè)不同元素中可重復(fù)地任取m個(gè)元素排成一列，不同的排

列種數(shù)有那種；

有限個(gè)重復(fù)元素的全排列：設(shè)n個(gè)元素由k個(gè)不同元素%,電,...,如組成，分

別有n1,%,…,々個(gè)(勺+%+…+%=〃)，那么這n個(gè)元素的全排列數(shù)為

n?

HI!?n1!?????久!

第3頁(yè)共82頁(yè)

可重組合：從n個(gè)不同元素中，任意可重復(fù)地選取m個(gè)元素，稱為n個(gè)不

同元素中取m個(gè)元素的可重組合，其種數(shù)為C'T

1.1.4.圓排列（僅給出結(jié)論，請(qǐng)自證之）

在"個(gè)不同元素中,每次取出m個(gè)元素排在一個(gè)圓環(huán)上，叫做一個(gè)圓排列（或

叫環(huán)狀排列）.圓排列有三個(gè)特點(diǎn)：（i）無頭無尾；（ii）按照同一方向轉(zhuǎn)換

后仍是同一排列；（iii）兩個(gè)圓排列只有在元素不同或者元素雖然相同，但元

素之間的順序不同，才是不同的圓排列.

在A=1%,%,%，…，4｝的"個(gè)元素中，每次取出m個(gè)不同的元素進(jìn)行圓排

Allt

列，圓排列數(shù)為A.

m

1.2.例題精講

1.2.1.板塊一利用加法、乘法原理以及枚舉方法計(jì)數(shù)

聯(lián)賽一試的填空題中出現(xiàn)的計(jì)數(shù)問題有接近一半的問題不需要用到很高深

的技巧，而是直接利用最基本的加法、乘法原理，以及枚舉方法來計(jì)數(shù).這主要

是考慮到有一部分參加聯(lián)賽的同學(xué)并未經(jīng)過專業(yè)的競(jìng)賽訓(xùn)練.雖然如此，這部分

計(jì)數(shù)問題枚舉起來往往分類復(fù)雜，需要小心仔細(xì).

從往年的聯(lián)賽試題來看，枚舉法解決計(jì)數(shù)問題是最主要的題型之一，其難點(diǎn)

在于做到''不重不漏”，這是加法原理的一個(gè)簡(jiǎn)單的應(yīng)用?枚舉過程中，采用恰

當(dāng)?shù)姆诸?、分步形式，往往?huì)收到化難為易的效果.

【例1】（高考難度的熱身問題）

（1）等腰三角形的三邊均為正整數(shù).它們周長(zhǎng)不大于10.這樣不同的三角

形的種數(shù)為

A.8B.9C.IOD.11

（2）有兩排座位，前排11個(gè)座位，后排12個(gè)座位，現(xiàn)安排2人就座,

規(guī)定前排中間的3個(gè)座位不能坐，并且這2人不左右相鄰，那么不同排法的種

數(shù)是

第4頁(yè)共82頁(yè)

A.234B.346C.350D.363

【解析】(1)設(shè)三邊為x,y,z,則x+y+z≤10,由三邊關(guān)系共有(1,1,1),(1,2,

2),(1,3,3),(1,4,4),(2,2,2),(2,2,3),(2,3,3),(2,4,4),(3,3,3),[3,

3,4)共10種.

(2)B前排中間的3個(gè)座位不能坐，有排法A，。，其中相鄰的分三類，在前排的其中的4個(gè)座位有

3封；則符合條件的排法種數(shù)中A務(wù)-3度-3A"11度=346,故選B(這是正難則反的思想，

從總體中除去不符合要求的)

另解：分三類：①兩人坐在前排，按要求有4?6+4?5=44種坐法.

②兩人坐在后排，按要求有：A：="。種坐法.

③兩人分別坐在前后排，有8×12×2=I92種

二共有346種排法.

【例2】(1)有多少個(gè)能被3整除而又含有數(shù)字6的五位數(shù)？

(2)集合｛1,2,...,100｝的子集中共有多少個(gè)至少包含一個(gè)奇數(shù)？

【解析】(1)按照上題正難則反的思想，可以先找出所有的五位數(shù)，共有90000

個(gè)，其中可被3整除的有30000個(gè)，下面研究這30000個(gè)數(shù)中不含數(shù)

字6的數(shù)，最高位有8種選擇，千、百、十位各有9種選擇，個(gè)位數(shù)除

不能為6外，還應(yīng)滿足恰各位數(shù)之和可被3整除，這恰有3種選擇，例

如當(dāng)前四位除以3余2時(shí)，個(gè)位應(yīng)為1,4,7之一；故能被3整除且不含

數(shù)字6的有8χ9χ9χ9χ3=17496個(gè)，故所求五位數(shù)有

30000-17496=12504個(gè)

(2)顯然全部子集數(shù)為2ωo個(gè)，不包含任何奇數(shù)的子集即

｛2,4,6,...,98,100)的子集共有25°個(gè)，故所求子集個(gè)數(shù)為2⑼-250個(gè).(思

考：請(qǐng)用最簡(jiǎn)潔的方法確定為何n元集合子集數(shù)為2"個(gè))

【例3】設(shè)ABCDEF為正六邊形，一只青蛙開始在頂點(diǎn)4處，它每次可隨意地跳

到相鄰兩頂點(diǎn)之一.若在5次之內(nèi)跳到。點(diǎn)，則停止跳動(dòng)；若5次之內(nèi)

不能到達(dá)。點(diǎn)，則跳完5次也停止跳動(dòng)，那么這只青蛙從開始到停止，

可能出現(xiàn)的不同跳法共種

【解析】這是標(biāo)準(zhǔn)的聯(lián)賽風(fēng)格的枚舉問題，所謂殺雞焉用牛刀，用遞歸方法來解

這類問題就太麻煩了.

第5頁(yè)共82頁(yè)

顯然青蛙不能跳1,2,4次到達(dá)D點(diǎn)，于是青蛙的跳法只有以下兩種：

（1）青蛙跳3次后到達(dá)D點(diǎn)，有2種跳法；

（2）青蛙跳5次后停止，跳3次有23-2種，后兩次有22種，共計(jì)24

種；

所以，合計(jì)有26種跳法

注本題為1997年聯(lián)賽試題

【例4】從給定的六種不同顏色中選用若干種顏色，將一個(gè)正方體的六個(gè)面染

色，每面恰染一種顏色，每?jī)蓚€(gè)具有公共棱的面染成不同的顏色。則不

同的染色方法共有種。（注：如果我們對(duì)兩個(gè)相同的正方體

染色后，可以通過適當(dāng)?shù)姆D(zhuǎn)，使得兩個(gè)正方體的上、下、左、右、前、

后六個(gè)對(duì)應(yīng)面的染色都相同，那么，我們就說這兩個(gè)正方體的染色方案

相同。）

【解析】因?yàn)橛泄岔旤c(diǎn)的三個(gè)面互不同色，故至少要用3種顏色，下面分四種

情形來考慮.

（1）6種顏色都用時(shí)，現(xiàn)將染某種固定顏色的面朝上，從剩下5種顏色中

取一種顏色染下底面有種方法，余下4種顏色染四個(gè)側(cè)面（應(yīng)是4種顏色的

圓排列）有3!種方法.所以不同的染色方案有3!=30種.

（2）只用5種顏色時(shí)，從6種顏色中取5種顏色有種方法，這時(shí)必有

一組對(duì)面同色.從5種顏色中取一種顏色染一組對(duì)面,并將它們朝上和朝下,有C；

種方法，其余4種顏色染四個(gè)側(cè)面（應(yīng)是4種不同顏色的鏈排列）有Lχ3!種

2

方法.所以不同的染色方案有C；?C][?3!=90種.

（3）只用4種顏色時(shí)，從6種顏色中取4種顏色有C：種方法，這時(shí)必有

兩組對(duì)面同色，另一組對(duì)面不同色，將不同色的一組對(duì)面朝上和朝下，并從4

種顏色中取兩種顏色染上、下底面，有種方法，其余兩種顏色染四個(gè)側(cè)面且

使兩組對(duì)面同色（應(yīng)是兩種不同顏色的鏈排列），只有1種方法.所以不同的染

色方案有C：?C>1=9O種.

第6頁(yè)共82頁(yè)

(4)只用3種顏色時(shí)，從6種顏色中取3種顏色有C；種方法，這時(shí)三組

對(duì)面都同色，用三種顏色去染它們只有1種方法.所以不同的染色方案有

C>1=20種.

綜上可知，不同的染色方案共有30+90+90+20=230種.

注本題為1996年聯(lián)賽試題，是歷年來一試計(jì)數(shù)問題中最復(fù)雜的一道，其背景

與波利亞群論計(jì)數(shù)原理有關(guān)，這遠(yuǎn)遠(yuǎn)超出了高中范圍，此處略去

【例5】將24個(gè)志愿者名額分配給3個(gè)學(xué)校，則每校至少有一個(gè)名額且各校名

額互不相同的分配方法共有222種.

【解析】用4條棍子間的空隙代表3個(gè)學(xué)校，而用*表示名額.如

I****I**∣**∣

表示第一、二、三個(gè)學(xué)校分別有4,18,2個(gè)名額.

若把每個(gè)“*"與每個(gè)"|”都視為一個(gè)位置，由于左右兩端必須是“I”，故不同

的分配方法相當(dāng)于24+2=26個(gè)位置(兩端不在內(nèi))被2個(gè)“I”占領(lǐng)的一種"占位

法

"每校至少有一個(gè)名額的分法"相當(dāng)于在24個(gè)"*”之間的23個(gè)空隙中選出2

個(gè)空隙插入"I",故有C?=253種.

又在"每校至少有一個(gè)名額的分法”中“至少有兩個(gè)學(xué)校的名額數(shù)相同”的分

配方法有31種.

綜上知，滿足條件的分配方法共有253—31=222種.

［解法二］設(shè)分配給3個(gè)學(xué)校的名額數(shù)分別為由,x2,鼻，則每校至少有一個(gè)名額的

分法數(shù)為不定方程

xl+x2+X3=24.

的正整數(shù)解的個(gè)數(shù)，即方程%+々+退=21的非負(fù)整數(shù)解的個(gè)數(shù)，它等于3個(gè)不

同元素中取21個(gè)元素的可重組合：

H；=《；=《=253.

又在“每校至少有一個(gè)名額的分法”中“至少有兩個(gè)學(xué)校的名額數(shù)相同”的分

配方法有31種.

綜上知，滿足條件的分配方法共有253—31=222種

第7頁(yè)共82頁(yè)

注本題為2008年聯(lián)賽試題，從近年來聯(lián)賽一試組合問題來看，組合計(jì)數(shù)問題

難度明顯降低了.本題所應(yīng)用的插空法是一種在高考和競(jìng)賽中常用的計(jì)數(shù)方法

【例6】將2個(gè)α和2個(gè)b共4個(gè)字母填在4x4方格表內(nèi)，每個(gè)小方格內(nèi)至多填

1個(gè)字母，若使相同字母既不同行也不同列，則不同的填法共有

種（用數(shù)字作答）。

【解析】使2個(gè)α既不同行也不同列的填法有GM42=72種，同樣，使2個(gè)b既

不同行也不同列的填法也有C4242=72種，故由乘法原理，這樣的填法

共有722種，其中不符合要求的有兩種情況：2個(gè)α所在的方格內(nèi)都填

有b的情況有72種；2個(gè)α所在的方格內(nèi)僅有1個(gè)方格內(nèi)填有b的情

況有Ci6M92=16χ72種。所以，符合題設(shè)條件的填法共有

722-72-16×72=3960種。

注本題為2007年聯(lián)賽第12題

【例7】設(shè)三位數(shù)〃=詼，若以a,b,c為三條邊的長(zhǎng)可以構(gòu)成一個(gè)等腰（含等

邊）三角形，則這樣的三位數(shù)n有（）

A.45個(gè)B.81個(gè)C165個(gè)D.216個(gè)

【解析】本題是標(biāo)準(zhǔn)的枚舉問題，情況繁多.

a,b,c要能構(gòu)成三角形的邊長(zhǎng)，顯然均不為0。即α,b,c∈{l,2,...,9}

（1）若構(gòu)成等邊三角形，設(shè)這樣的三位數(shù)的個(gè)數(shù)為〃「由于三位數(shù)中三個(gè)數(shù)碼

都相同，所以，々=C；=9。

（2）若構(gòu)成等腰（非等邊）三角形，設(shè)這樣的三位數(shù)的個(gè)數(shù)為〃2,由于三位數(shù)

中只有2個(gè)不同數(shù)碼。設(shè)為a、b,注意到三角形腰與底可以置換，所以可取的

數(shù)碼組（a,b）共有2C；。但當(dāng)大數(shù)為底時(shí)，設(shè)a>b,必須滿足A<α<乃。此

時(shí)，不能構(gòu)成三角形的數(shù)碼是

a987654321

4,34,33,23,2

b1,21,211

2,12,111

共20種情況。

第8頁(yè)共82頁(yè)

同時(shí)，每個(gè)數(shù)碼組（a,b）中的二個(gè)數(shù)碼填上三個(gè)數(shù)位，有C；種情況。

故4=C；（2C；-20）=6（C；-IO）=I56。綜上，n=nl+n2=?65o

注本題為2004年聯(lián)賽試題

1.2.2.板塊二映射與對(duì)應(yīng)方法

由一一映射的定義可知，若存在從集合M到N的一一映射，則IMl=IM.于是

在難以直接計(jì)算集合M中元素個(gè)數(shù)時(shí)，我們可以設(shè)法構(gòu)造這樣一個(gè)映射，將問

題轉(zhuǎn)化為計(jì)算較為容易計(jì)算的集合N的元素個(gè)數(shù).基于這種兩集合元素一一對(duì)應(yīng)

的特點(diǎn)，也稱為“配對(duì)法”

【例8】（1）試用對(duì)應(yīng)方法證明可重組合公式：從n個(gè)不同元素中，任意可重

復(fù)地選取m個(gè)元素，稱為n個(gè)不同元素中取m個(gè)元素的可重組合，其

種數(shù)為C2τ

（2）證明：不定方程占+當(dāng)+…+4="（k,n為正整數(shù)）的非負(fù)整數(shù)解

組數(shù)為

【解析】（1）設(shè)n個(gè)元素為1,2,并設(shè)取出的m個(gè)元素為

l

?≤ax≤a2≤...≤am≤n,^J?l<<2l+0<α2+l<...<am+m-?≤n+m-?,

作對(duì)應(yīng)

（01,a2,...,am）÷÷（αl+0,a2+l,...,am+m-↑）,易證明它為---

對(duì)應(yīng)

后者為從〃+〃2-1個(gè)元素中取m個(gè)元素的組合數(shù)a，-,故得證

（2）將n個(gè)圓圈與k-l個(gè)豎線排成一排，k-1個(gè)豎線將n個(gè)圓圈依次

分成k個(gè)部分：x,,x2,...,xk,易見不同的排列對(duì)應(yīng)不定方程不同的解，易證它為

一個(gè)一一對(duì)應(yīng)，而在n+k-1個(gè)元素中取出k-l個(gè)的全排列數(shù)為,故得證.

【例9】凸n邊形的任意3條對(duì)角線不相交于形內(nèi)一點(diǎn)，求其對(duì)角線在形內(nèi)的交

點(diǎn)總個(gè)數(shù).

第9頁(yè)共82頁(yè)

【解析】任一形內(nèi)交點(diǎn)對(duì)應(yīng)兩條對(duì)角線Lm;反之，任意兩條對(duì)角線唯一確定形內(nèi)

一個(gè)交點(diǎn)P,從而P與(?,m)構(gòu)成一一對(duì)應(yīng)；又任一對(duì)角線對(duì)應(yīng)形內(nèi)2

頂點(diǎn)，n邊形中任取4頂點(diǎn)即可唯一確定兩對(duì)角線，于是有如下一一對(duì)

應(yīng)：點(diǎn)P<→(/,加)—(A,B,CO)

于是交點(diǎn)總個(gè)數(shù)=四頂點(diǎn)組個(gè)數(shù)=C：

注本題為組合數(shù)學(xué)一個(gè)重要分支一一組合幾何中的非常重要的一個(gè)結(jié)論，可以

利用它解決一些高難度的組合幾何計(jì)數(shù)問題

【例10】將集合A中的n個(gè)元素排成一行，若某個(gè)子集中任意兩元素不相鄰，則

稱此子集為不好的，試證明：k元的不好的子集個(gè)數(shù)為c3.∣

【解析】設(shè)n個(gè)元素排成一行依次為為1,2,并設(shè)取出的k個(gè)元素為

1≤Z1<Z2<...<4≤n,

顯然有2≤

作變換l≤i∣<i2T<i3-2???<%-(A-l)W"-k+l,并取序列：

(il,i2-l,i3-2,...,it-(k-l))r它是1,2,n-k+1中的一個(gè)嚴(yán)格上升的序列

作對(duì)應(yīng)--

—(z1,∕2l,??2,...,ZA.—(?—1)),

易證明它為一一對(duì)應(yīng)，且后者的種數(shù)為從〃-Z+1個(gè)元素中取k個(gè)元素

的組合數(shù)CM…故得證

注本題為第16屆普特南競(jìng)賽題

Q大顯身手

1.(1)在100件產(chǎn)品中有6件次品，現(xiàn)從中任取3件產(chǎn)品，至少有1件

次品的不同取法的種數(shù)是

A.CgCg4B.C：C；9

C?G'oo—C94D.AOO-A94

(2)從4名男生和3名女生中選出4人參加某個(gè)座談會(huì)，若這4人中

必須既有男生又有女生，則不同的選法共有

第10頁(yè)共82頁(yè)

A.140種B.120種C35種D.34種

【解析】（1）C任取3件產(chǎn)品有Ca）種方法，其中無次品有C；4種方法，故至少有1件次品的

方法數(shù)為q%）-Cg4?

（2）D既有女生又有男生，可以分類表示，三男一女有或?以種選法，二

男二女有盤或種，

一男三女有以?或種選法，則總的不同的選法有

c∣?cj+c^?cf+cj?=34（種）

2.由三個(gè)數(shù)字1、2、3組成的5位數(shù)中，1、2、3都至少出現(xiàn)1次,

這樣的5位數(shù)共有多少個(gè)？

【解析】在5位數(shù)中，若1只出現(xiàn)1次，有Ge+C：+C：）=70個(gè)；

若1只出現(xiàn)2次，有C；（C；+C；）=60個(gè)；

若1只出現(xiàn)3次，有=20個(gè).則這樣的五位數(shù)共有150個(gè).故

填150個(gè).

注本題為05年江蘇省預(yù)賽試題

3.已知集合A=N5x-a<θ},B—{Λ∣6X-?>θ},a,b∈N,且

AnfinTV={2,3,4）-則整數(shù)對(duì)（。,勸的個(gè)數(shù)為

A.20B.25C.30D.42

【答】（）

Z7b_

【解析】由5x-a<0=x<-；6x-Z?>0=>x>—。要使ACBCN={2,3,4},

56

《<2

6≤b<?2

則即《所以數(shù)對(duì)（α,乃共有Ce=30。

4個(gè)52Q≤a<25

注本題為2006年聯(lián)賽試題

4.記集合T={O,1,2,3,4,5,6},M=[4+?→與+2q∈T,i=l,2,3,4,將M

77^TT

中的元素按從大到小順序排列，則第2005個(gè)數(shù)是

第11頁(yè)共82頁(yè)

“5563c5562cli04n

a?~+ψ+ψ+ψB.-+ψ+ψ+ψC.-+ψ+ψ+ψD.

1103

7+7τ+7y+7τ

【解析】用Ua2…41P表示k位P進(jìn)制數(shù)，將集合M中的每個(gè)數(shù)乘以7，

得

r32

M={?,?7+a2?7+α3?7+(a4Iɑ?∈T,z=：1,2,3,4}={[αlα2π3π4]7?ai≡T,i-1,2,3,4).

M'中的最大數(shù)為[6666b=[24001。。

在十進(jìn)制數(shù)中，從2400起從大到小順序排列的第2005個(gè)數(shù)是

2400-2004=396;

而[396Lo=U網(wǎng)7,將此數(shù)除以7t便得到M中的數(shù)：,*+*+*故

選Co

注本題為2005年聯(lián)賽試題，題目形式提示我們，要采用進(jìn)制轉(zhuǎn)換.事實(shí)上，這

類題目在小學(xué)和初中是極為常見的.

5.已知兩個(gè)實(shí)數(shù)集合A={αι,α2,…,Qioo}與8={歷,歷,…力5θ},若從A到B的映

射/使得B中每個(gè)元素都有原象，且

f[aι)≤∕(Q2]≤???≤∕[0ιoo)

則這樣的映射共有

網(wǎng)端(B)喘(C)瑞(D)噫

【解析】不妨設(shè)bι<b2<…<b50,將A中元素aι,a2,…，aιoo按順序分為非空

的50組，定義映射f：A-B,使得第i組的元素在f之下的象都是bi

(i=l,2,…,50),易知這樣的f滿足題設(shè)要求，每個(gè)這樣的分組都一一對(duì)應(yīng)

滿足條件的映射，于是滿足題設(shè)要求的映射f的個(gè)數(shù)與A按足碼順序分

為50組的分法數(shù)相等，而A的分法數(shù)為則這樣的映射共有C；；,

故選D。

注本題為2002年全國(guó)聯(lián)賽試題

第12頁(yè)共82頁(yè)

6.在世界杯足球賽前，F(xiàn)國(guó)教練為了考察Ai,A2,…,A7這七名，準(zhǔn)備讓他們

在三場(chǎng)訓(xùn)練比賽(每場(chǎng)90分鐘)都上場(chǎng)，假設(shè)在比賽的任何時(shí)刻，這些

中有且僅有一人在場(chǎng)上，并且Ai,A2,A3,A4每人上場(chǎng)的總時(shí)間(以分鐘為

單位)均被13整除，如果每場(chǎng)換人次數(shù)不限，那么按每名隊(duì)員上場(chǎng)的總

時(shí)間計(jì)算，共有多少種不同的情況。

【解析】設(shè)第i名隊(duì)員上場(chǎng)的時(shí)間為Xi分鐘(i=123,…,7),問題即求不定方程

Xl+X2+…+X7=270

①

在條件7∣Xi(IWiW4)且13∣Xj(5≤jW7)下的正整數(shù)解的級(jí)數(shù)。

若(XI,X2,…,X7)是滿足條件①的一組正整數(shù)解，則應(yīng)有

47

Z?x,.=7mZXj=I3nm,n∈N

i=1j=5

.?.m,n是不定方程

7m+13n=270

②

在條件m>4且n≥3下的一組正整數(shù)解。.......

10分

'/7(m-4)+13(n-3)=203

令m,=m-4n,=n-3有

7m'+13n,=270

③

求②滿足條件mN4且n≥3的正整數(shù)解等價(jià)于求③的非負(fù)整數(shù)解。

易觀察到7?2+13?(-1)=1

,7?406+13-(-203)=203

即mo=4O6no=-203是③的整數(shù)解

/.③的整數(shù)通解為

m,=406-13kn,=-203+7kk∈Z

令m,20n,20,解得29≤k≤31..................

20分

取k=29,30,31得到③滿足條件的三組非負(fù)整數(shù)解：

第13頁(yè)共82頁(yè)

m,=29mf=16m,=3

n,=On,=7n—14

從而得到②滿足條件的三組正整數(shù)解：

m-33[m-20?m-7

\1\................30

〃=3[n=10[〃=17

分

1)在m=33,n=3時(shí)，顯然X5=X6=X7=13僅有一種可能，

又設(shè)Xi=7yi(i=L2,3,4),于是由不定方程yι+y2+y3+y4=33有C數(shù)=Cf2=4960

組正整數(shù)解。

，此時(shí)①有滿足條件的《2=4960組正整數(shù)解。

2)在m=20,n=10時(shí)，設(shè)Xi=7yi(i=l,2,3,4),xj=13yj(j=5,6,7)

由yi+y2+y3+y4=20,有G*9組正整數(shù)解；以及y5+y6+y7=10,有組正整數(shù)

解。

.?.此時(shí)①有滿足條件的C：9?《=34884組正整數(shù)解。

3)在m=7,n=17時(shí)，設(shè)Xi=7yi(i=l,2,3,4),xj=l3yj(j=5,6,7)

由y1+y2+y3+y4=7,有Ci組正整數(shù)解；以及y5+y6+y7=17,有G；組正整數(shù)

解。.......40分

綜上所述，①滿足條件的正整數(shù)解的組數(shù)為

Cl2+Cf9?C?+ee?Gi=4960+34884+2400=42244................50分

注本題為2002年聯(lián)賽二試最后一題，是一道不是很難的組合數(shù)論問題.問題求

解過程中多次用到了我們的例8的結(jié)論.

第14頁(yè)共82頁(yè)

2.第二講組合計(jì)數(shù)（2）

2.1.本講概述

組合計(jì)數(shù)的方法很多，除了上一講的枚舉、對(duì)應(yīng)方法之外還包括：算兩次、

遞推方法、容斥原理、利用恒等式、母函數(shù)方法等；容斥原理的方法將在第四

講講述，遞推方法我們?cè)跀?shù)列部分單獨(dú)講述.本講主要討論利用算兩次方法計(jì)數(shù)

的問題以及較為簡(jiǎn)單的遞推方法（因?yàn)槲覀儠翰痪邆渫晟频倪f推數(shù)列知識(shí)）；

另外，本講還將涉及到組合計(jì)數(shù)的二試與冬令營(yíng)級(jí)別難度的少數(shù)問題.

首先給出本講問題中要用到的知識(shí)（雖然這些知識(shí)可能暫時(shí)沒有學(xué)到，但本

講只需會(huì)用即可）：

二項(xiàng)式定理：（χ+y）"=2c*iy",特別地，（l+χ）"=NGW,其中〃∈W

Jl=Ok=0

特征方程與數(shù)列通項(xiàng)：

記一列數(shù)卬,。2,……為數(shù)列｛aj，如果它滿足a”+2=Pan+1+qall,（n≥V）,那

么稱χ2=pχ+q為此數(shù)列的特征方程，（1）當(dāng)有兩互異實(shí)根時(shí)，數(shù)列通項(xiàng)為

Clll=GC-X∣'+β?χ'1↑

（2）當(dāng)有二等根時(shí),數(shù)列通項(xiàng)為％=（α+以）*

其中α,4為根據(jù)初值確定的待定系數(shù)

2.2.例題精講

2.2.1.板塊一算兩次

算兩次是一種非常重要的思想方法，在代數(shù)、組合、幾何中都有涉及.組合

問題中，組合極值、組合不等式也常常涉及到算兩次.組合計(jì)數(shù)中，在直接計(jì)算

第15頁(yè)共82頁(yè)

非常復(fù)雜甚至無從入手時(shí)，我們常常利用算兩次方法.顧名思義，算兩次是指用

不同的方法或者從不同的角度對(duì)同一個(gè)量進(jìn)行計(jì)算，當(dāng)兩次都得到精確值時(shí)，

我們就得到一個(gè)等式，當(dāng)為估計(jì)式時(shí)，我們就得到一個(gè)不等式.事實(shí)上，數(shù)學(xué)中

有相當(dāng)大一部分定理就是利用算兩次思想對(duì)原有的問題進(jìn)行剖析，得到新的內(nèi)

在關(guān)系式.

【例11】設(shè)…，4,為1，2,…，n的一個(gè)排列，人是集合?<α*,i>k｝元

素的個(gè)數(shù)，而g*是集合｛q∣4>%,i<左｝元素的個(gè)數(shù)（左=1,2,…，證

明Szt=SW

k=lk=?

【解析】考慮集合S=｛（q,%）∣q?<%,i>左｝的元素個(gè)數(shù)網(wǎng)。一方面，固定攵先對(duì)i

求和，然后再對(duì)左求和，得IS卜t∕t；另一方面，固定i先對(duì)左求和，

k=?

然后再對(duì)i求和，又得到∣s∣=fg產(chǎn)5gi所以得力Z=E>一

/=I?=1A=Ik=l

注本題只是為了說明算兩次的基本思想和方法，這里的計(jì)數(shù)是抽象的，這種方

法相當(dāng)于考慮各個(gè)分量對(duì)總體的“貢獻(xiàn)”，因此也有人把它叫做“貢獻(xiàn)法”.請(qǐng)

參考習(xí)題第一題

【例12】有n粒小球，任意將其分成兩堆，求出兩堆球數(shù)之積，再將其中一堆任

意地分成兩堆，求出此兩堆之積，如此下去，直至將小球分成n堆（每

個(gè)球1堆）為止.記此過程中所有的乘積之和為S,求S的所有可能值.

【解析】以n=8為例，不論如何分，最后總得到S=28=Cj,于是猜想對(duì)一般情

形總有S=C3即n粒小球中任取兩個(gè)組成小球?qū)Φ膫€(gè)數(shù)；另一方面，

每將一些小球分成兩堆，就將原來的一些小球?qū)Γ僭O(shè)只有同一堆才能

組成小球?qū)Γ┎痖_，拆開的數(shù)目恰為兩堆個(gè)數(shù)之積，最終的小球?qū)€(gè)數(shù)

為0,從而乘積之和即為最初的小球?qū)€(gè)數(shù)，故得證.

注本題構(gòu)造了一種巧妙的對(duì)應(yīng)，使原來無法下手的問題變得有章可循.事實(shí)上,

組合問題，特別是算兩次問題最關(guān)鍵的就是尋找算兩次的對(duì)象，本題中就是對(duì)

第16頁(yè)共82頁(yè)

小球?qū)M(jìn)行算兩次，使得問題清晰明了.

【例13】一張正方形紙片內(nèi)有IOOO個(gè)點(diǎn)，這些點(diǎn)及正方形的頂點(diǎn)中任意3點(diǎn)不

共線.在這些點(diǎn)及正方形的頂點(diǎn)間連一些線段將正方形全部分成小三角

形(它們都以所連線段及正方形的邊為邊，且所連線段除端點(diǎn)外兩兩無

公共點(diǎn)).問一共連有多少條線段，一共得到多少個(gè)三角形？

【解析】設(shè)一共連有/條線段，得到k個(gè)三角形.

首先對(duì)角度和進(jìn)行計(jì)數(shù)：一方面,所得k個(gè)三角形的內(nèi)角和為Z?18O；

另一方面，計(jì)算IOOO個(gè)內(nèi)點(diǎn)及4個(gè)正方形頂點(diǎn)處內(nèi)角和為

1000?360+4.90,從而算得k=2002;

其次，對(duì)邊數(shù)進(jìn)行計(jì)數(shù)：k個(gè)三角形共3k條邊，另一方面，每條線段

是兩個(gè)三角形的公共邊，正方形的每條邊被計(jì)算1次，共2/+4條邊，

從而2/+4=3左，得到/=3001

注本題的背景是計(jì)算機(jī)圖形學(xué)中著名的三角面片分劃問題，這類問題在馮康先

生的有限元中也有應(yīng)用.

從本題及習(xí)題2可以得到計(jì)算這類問題的一般方法，即對(duì)邊、角乃至同色角、

異色角等元素進(jìn)行計(jì)數(shù).

【例14](選講)能否把1,1,2,2,3,3,…，1986,1986這些數(shù)排成一行，使得

兩個(gè)1之間夾著1個(gè)數(shù)，兩個(gè)2之間夾著2個(gè)數(shù)，兩個(gè)1986之間夾著

1986個(gè)數(shù)？

【解析】設(shè)能將上述數(shù)字排成一行滿足題設(shè)，這是每一個(gè)數(shù)i(l≤i≤1986)可賦予

它一對(duì)有序?qū)崝?shù)(與上)作為坐標(biāo)，這里坐標(biāo)值分別為它第一次與第二次

出現(xiàn)的位置序號(hào).顯然有關(guān)系：χ=x,.+z+l.

現(xiàn)用兩種方法計(jì)算全體數(shù)的坐標(biāo)和：

2x1986

一方面，直接從整體看，坐標(biāo)和為Zk=I986x(2x1986+1)為偶數(shù)；

k=?

另一方面，就某一個(gè)i,兩坐標(biāo)和為2x,?+i+l,從而所有坐標(biāo)和為

198619861986

Z(2x,.+ι+l)=2∑x,.+∑z+l986=偶數(shù)+993×1987為奇數(shù).此兩者顯

Z=IZ=I/=1

第17頁(yè)共82頁(yè)

然矛盾

注本題為第二屆冬令營(yíng)的一道很難的問題,方法較多，上面給出的方法是一個(gè)

很巧妙的解法，利用奇偶性導(dǎo)出了矛盾，是命題人所沒有想到的.

2.2.2.板塊二遞推方法

當(dāng)所計(jì)數(shù)對(duì)象按從1到n有規(guī)律出現(xiàn)時(shí)，可視之為一個(gè)數(shù)列并考察其相鄰項(xiàng)

之間關(guān)系，得到遞推關(guān)系式,進(jìn)而利用數(shù)列知識(shí)進(jìn)行求解.一般來說，這類問題

的關(guān)鍵在于如何得到遞推關(guān)系式.對(duì)于競(jìng)賽選手而言，由組合問題的遞推關(guān)系式

得到通項(xiàng)總是很簡(jiǎn)單的，因?yàn)榻M合問題的特性決定了遞推關(guān)系式不會(huì)太過復(fù)雜.

由于我們沒有詳細(xì)講述數(shù)列通項(xiàng)求法，所以這里只給出較為簡(jiǎn)單的問題.

注：建議教師主要講述如何由題目條件得到遞推式，至于遞推式求解可以淡

化或者讓學(xué)生自行求解

【例15】（FibOnaCCi數(shù)列）假設(shè)一對(duì)兔子每隔一月生一對(duì)小兔，每對(duì)小兔兩個(gè)

月后也逐月生一對(duì)小兔，如年初時(shí)放一對(duì)成年兔，那么一年以后兔房中

有多少只兔子？

【解析】用%表示第n個(gè)月初的小兔對(duì)數(shù),易得到“∣=l,α2=2,。3=3,…

一般地，第n個(gè)月初的小兔分為兩部分：第n-1個(gè)月的兔子數(shù)與第n個(gè)

月初出生的小兔對(duì)數(shù)，

即得到遞推式由特征方程的結(jié)論及初值，可得到

"13=377

注關(guān)于斐波那契數(shù)列的進(jìn)一步知識(shí)我們到數(shù)列部分再詳細(xì)講述

【例16】用1,2,3來構(gòu)造一個(gè)n位數(shù)，但不允許數(shù)位中出現(xiàn)兩個(gè)連續(xù)的1,問這

樣的數(shù)有多少個(gè)？

【解析】設(shè)有α“個(gè)，顯然。產(chǎn)3,。2=8，討論：

若n位數(shù)第一位不是1,那么后面可以隨便寫，于是這樣的有20,τ個(gè),

若第一位是1,第二位寫2或3,第三位后可以隨便寫，于是這樣的有

第18頁(yè)共82頁(yè)

2α,τ個(gè)，

得到遞推式“z,=2α,ι+2α.2,"N3,由特征方程的結(jié)論及初值，化簡(jiǎn)得

到

+22

βn=^((l+√3Γ-(l-^Γ)

注一般寫出原始結(jié)果即可，或者把化簡(jiǎn)結(jié)果同時(shí)寫出

2.2.3.板塊三組合計(jì)數(shù)綜合問題

【例17】設(shè)r,SJ為整數(shù)，集合伍|。=2，+2'+2，,03<5<廠｝中的數(shù)由小到大組

成數(shù)列｛七｝：7,11,13,14,…，則=131。

【解析】?；r,s,t為整數(shù)且O≤f<s<r,.?.r最小取2,此時(shí)符合條件的數(shù)有C；=1

廠=3,SJ可在0,1,2中取，符合條件有的數(shù)有C；=3

同理，r=4時(shí)，符合條件有的數(shù)有C：=6

r=5時(shí)，符合條件有的數(shù)有C；=10

r=6時(shí)，符合條件有的數(shù)有C；=15

r=7時(shí)，符合條件有的數(shù)有C；=21

因此，/6是尸=7中的最小值，即—=2°+2∣+2,=131

注本題為2005年四川預(yù)賽題，事實(shí)上此題源自2003年全國(guó)高考理科試卷壓

軸題，用二進(jìn)制方法求解最為方便，可參考左曉明《2003年高考理科數(shù)學(xué)壓軸

題的一種巧妙解法及其推廣》中學(xué)教研2003.12

【例18】如果自然數(shù)α的各位數(shù)字之和等于7,那么稱。為“吉祥數(shù)”.將所有“吉

祥數(shù)”從小到大排成一列，…，若可=2005,則。5"=-

【解析】準(zhǔn)確理解“吉祥數(shù)”的定義是解題的前提，根據(jù)題意，可將此計(jì)數(shù)問題

轉(zhuǎn)化為考慮不定方程的非負(fù)整數(shù)解的個(gè)數(shù).

?.?方程m+/+???+4=機(jī)的非負(fù)整數(shù)解的個(gè)數(shù)為e??.而使

項(xiàng)》,工工0(摩2)的整數(shù)解的個(gè)數(shù)為。黑_2-現(xiàn)取機(jī)=7,可知，攵位“吉祥數(shù)”

第19頁(yè)共82頁(yè)

的個(gè)數(shù)為P(Z)=C3?

?.?2005是形如五反的數(shù)中最小的一個(gè)“吉祥數(shù)”，且

P(I)=C；=1,P(2)==7,P(3)==28,

對(duì)于四位“吉祥數(shù)”嬴，其個(gè)數(shù)為滿足α+匕+c=6的非負(fù)整數(shù)解個(gè)數(shù)，即

%τ=28個(gè).

.?.2005是第1+7+28+28+1=65個(gè)“吉祥數(shù)”,即-=2005.從而

n—65,5〃=325.

5

又P(4)=《=84,R5)=Cf0=210,而EP(k)=330.

k=?

???從大到小排列的最后六個(gè)五位“吉祥數(shù)”依次是：70000,

61000,60100,60010,60001,52000.

,第325個(gè)“吉祥數(shù)”是52000,即a5n=520∞.

注1、本題為2005年全國(guó)聯(lián)賽試題

2、很多計(jì)數(shù)問題都可以轉(zhuǎn)化為求不定方程的解的組數(shù)，一般地，有

(1)不定方程內(nèi)+/+…+%=加的非負(fù)整數(shù)解的組數(shù)為

^n-?_「"I

tι+m-?-n+m-?；

(2)不定方程x∣+%+…+%=加的正整數(shù)解的組數(shù)為C；；O

【例19】若四位數(shù)〃="〃的各位數(shù)碼α,"c,d中，任三個(gè)數(shù)碼皆可構(gòu)成一個(gè)三

角形的三條邊長(zhǎng)，則稱〃為四位三角形數(shù)，試求所有四位三角形數(shù)的個(gè)

數(shù).

【解析】三個(gè)數(shù)構(gòu)成三角形的三條邊長(zhǎng)的充要條件是任意兩個(gè)數(shù)之和大于第三

個(gè)數(shù).本題需要根據(jù)四個(gè)數(shù)碼的各種可能情況分類進(jìn)行分析，按照四個(gè)

數(shù)碼取值個(gè)數(shù)的不同進(jìn)行分類比較容易入手一些.

稱Q"c,d)為〃的數(shù)碼組，則α,"c,deM={l,2,,9}.

(1)當(dāng)數(shù)碼組只含一個(gè)值，為(α,α,α,α),α=1,2,,9,共得9個(gè)〃值.

(2)當(dāng)數(shù)碼組恰含二個(gè)值a,。(a>b).

①數(shù)碼組為(a,a,a,。)型，則任取三個(gè)數(shù)碼皆可構(gòu)成三角形，對(duì)于每個(gè)

第20頁(yè)共82頁(yè)

a∈{2,,9),人可取a-1個(gè)值，則數(shù)碼組個(gè)數(shù)為苫5-1)=36,對(duì)于每組

a=2

(a,a,a,b),人有4種占位方式，于是這種〃有36x4=144個(gè).

②數(shù)碼組為(。力力，加型(a>∕?),據(jù)構(gòu)成三角形條件，有b<a<2b,

力的取值1234^5^6789

(b,2h)M中a的個(gè)012343210

數(shù)

共得16個(gè)數(shù)碼組，對(duì)于每組(a,份，。有4種占位方式，于是這種〃有

16x4=64個(gè).

③數(shù)碼組為(a,a,b,。)型Qa>b),據(jù)構(gòu)成三角形條件，有A<a<如，同上

得16個(gè)數(shù)碼組，對(duì)于每組(a,a力力)，兩個(gè)。有C；=6種占位方式，于是這種〃有

16x6=96個(gè).

以上共計(jì)144+64+96=304個(gè).

(3)當(dāng)數(shù)碼組恰含三個(gè)值a,"c(a>b>c).

①數(shù)碼組為3"c,c)型，據(jù)構(gòu)成三角形條件，則有c<8<a<2c,這種

(a,"c?,c)有14組，每組中a/有A：=12種占位方式，于是這種〃有14x12=168

個(gè).

②數(shù)碼組為(a,。,。,C)型，c<b<a<b+c,此條件等價(jià)于M={1,2,,9}中

取三個(gè)不同的數(shù)構(gòu)成三角形的方法數(shù)，有34組，每組中。力有A；=12種占位方

式,于是這種〃有34x12=408個(gè).

③數(shù)碼組為(a,a,。,C)型，c?<"<a<0+c,同情況②，有34A：=408個(gè)〃值.

以上共計(jì)168+408+408=984個(gè)〃值.

(4)a,8,c,d互不相同，WJWd<c<b<a<c+d>這種a,b,c,d有16組,

每組有4!種排法，共得16X4!=384個(gè)〃值.

綜上，全部四位三角形數(shù)