高一數(shù)學競賽講義第1~7講

高一數(shù)學競賽講義

目錄

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.第三講二項式定理與組合恒等式..............................................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頁共82頁

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

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

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

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

1.1.本講概述

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

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

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

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

成功完成組合問題的同學.因此，學習組合數(shù)學對于競賽獲獎以及數(shù)學能力的培

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

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

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

數(shù)學這門學科有一個初步的認識，為進一步學習打下基礎(chǔ)；3、了解部分冬令營

級別組合問題的難度與解題模式.

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

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

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

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

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

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

六、染色問題與操作問題

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

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

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

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

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

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

第2頁共82頁

1.1.1.加法原理與乘法原理

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

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

/=I

方法.

應(yīng)用加法原理的關(guān)鍵在于通過適當?shù)姆诸悾沟妹恳活惗枷鄬σ子谟嫈?shù).

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

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

/=I

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

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

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

1.1.2.無重排列與組合

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

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

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

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

(n-fn)!

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

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

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

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

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

可重排列：從n個不同元素中可重復地任取m個元素排成一列，不同的排

列種數(shù)有那種；

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

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

n?

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

第3頁共82頁

可重組合：從n個不同元素中，任意可重復地選取m個元素，稱為n個不

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

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

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

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

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

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

在A=1%,%,%，…，4｝的"個元素中，每次取出m個不同的元素進行圓排

Allt

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

m

1.2.例題精講

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

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

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

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

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

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

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

當?shù)姆诸悺⒎植叫问?，往往會收到化難為易的效果.

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

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

形的種數(shù)為

A.8B.9C.IOD.11

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

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

數(shù)是

第4頁共82頁

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個座位不能坐，有排法A，。，其中相鄰的分三類，在前排的其中的4個座位有

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

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

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

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

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

二共有346種排法.

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

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

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

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

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

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

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

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

30000-17496=12504個

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

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

考：請用最簡潔的方法確定為何n元集合子集數(shù)為2"個)

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

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

不能到達。點，則跳完5次也停止跳動，那么這只青蛙從開始到停止，

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

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

這類問題就太麻煩了.

第5頁共82頁

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

（1）青蛙跳3次后到達D點，有2種跳法；

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

種；

所以，合計有26種跳法

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

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

色，每面恰染一種顏色，每兩個具有公共棱的面染成不同的顏色。則不

同的染色方法共有種。（注：如果我們對兩個相同的正方體

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

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

相同。）

【解析】因為有公共頂點的三個面互不同色，故至少要用3種顏色，下面分四種

情形來考慮.

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

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

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

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

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

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

2

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

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

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

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

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

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

第6頁共82頁

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

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

C>1=20種.

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

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

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

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

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

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

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

表示第一、二、三個學校分別有4,18,2個名額.

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

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

法

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

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

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

配方法有31種.

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

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

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

xl+x2+X3=24.

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

同元素中取21個元素的可重組合：

H；=《；=《=253.

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

配方法有31種.

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

第7頁共82頁

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

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

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

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

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

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

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

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

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

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

722-72-16×72=3960種。

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

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

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

A.45個B.81個C165個D.216個

【解析】本題是標準的枚舉問題，情況繁多.

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

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

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

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

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

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

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

a987654321

4,34,33,23,2

b1,21,211

2,12,111

共20種情況。

第8頁共82頁

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

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

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

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

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

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

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

的特點，也稱為“配對法”

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

復地選取m個元素，稱為n個不同元素中取m個元素的可重組合，其

種數(shù)為C2τ

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

組數(shù)為

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

l

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

作對應(yīng)

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

對應(yīng)

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

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

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

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

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

點總個數(shù).

第9頁共82頁

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

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

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

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

于是交點總個數(shù)=四頂點組個數(shù)=C：

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

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

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

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

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

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中的一個嚴格上升的序列

作對應(yīng)--

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

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

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

注本題為第16屆普特南競賽題

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人參加某個座談會，若這4人中

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

第10頁共82頁

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.由三個數(shù)字1、2、3組成的5位數(shù)中，1、2、3都至少出現(xiàn)1次,

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

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

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

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

填150個.

注本題為05年江蘇省預賽試題

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

AnfinTV={2,3,4）-則整數(shù)對（。,勸的個數(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ù)對（α,乃共有Ce=30。

4個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個數(shù)是

第11頁共82頁

“5563c5562cli04n

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

1103

7+7τ+7y+7τ

【解析】用Ua2…41P表示k位P進制數(shù)，將集合M中的每個數(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。。

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

2400-2004=396;

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

選Co

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

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

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

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

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è)要求，每個這樣的分組都一一對應(yīng)

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

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

故選D。

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

第12頁共82頁

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

在三場訓練比賽(每場90分鐘)都上場，假設(shè)在比賽的任何時刻，這些

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

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

時間計算，共有多少種不同的情況。

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

Xl+X2+…+X7=270

①

在條件7∣Xi(IWiW4)且13∣Xj(5≤jW7)下的正整數(shù)解的級數(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ù)解等價于求③的非負整數(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得到③滿足條件的三組非負整數(shù)解：

第13頁共82頁

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時，顯然X5=X6=X7=13僅有一種可能，

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

組正整數(shù)解。

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

2)在m=20,n=10時，設(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ù)

解。

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

3)在m=7,n=17時，設(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頁共82頁

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

2.1.本講概述

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

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

講講述，遞推方法我們在數(shù)列部分單獨講述.本講主要討論利用算兩次方法計數(shù)

的問題以及較為簡單的遞推方法（因為我們暫不具備完善的遞推數(shù)列知識）；

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

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

講只需會用即可）：

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

Jl=Ok=0

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

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

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

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

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

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

2.2.例題精講

2.2.1.板塊一算兩次

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

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

第15頁共82頁

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

不同的方法或者從不同的角度對同一個量進行計算，當兩次都得到精確值時，

我們就得到一個等式，當為估計式時，我們就得到一個不等式.事實上，數(shù)學中

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

在關(guān)系式.

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

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

明Szt=SW

k=lk=?

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

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

k=?

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

/=I?=1A=Ik=l

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

法相當于考慮各個分量對總體的“貢獻”，因此也有人把它叫做“貢獻法”.請

參考習題第一題

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

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

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

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

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

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

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

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

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

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

第16頁共82頁

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

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

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

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

公共點).問一共連有多少條線段，一共得到多少個三角形？

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

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

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

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

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

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

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

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

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

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

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

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

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

1986個數(shù)？

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

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

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

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

2x1986

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

k=?

另一方面，就某一個i,兩坐標和為2x,?+i+l,從而所有坐標和為

198619861986

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

Z=IZ=I/=1

第17頁共82頁

然矛盾

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

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

2.2.2.板塊二遞推方法

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

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

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

得到通項總是很簡單的，因為組合問題的特性決定了遞推關(guān)系式不會太過復雜.

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

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

化或者讓學生自行求解

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

月后也逐月生一對小兔，如年初時放一對成年兔，那么一年以后兔房中

有多少只兔子？

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

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

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

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

"13=377

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

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

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

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

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

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

第18頁共82頁

2α,τ個，

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

到

+22

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

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

2.2.3.板塊三組合計數(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ù)有C；=1

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

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

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

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

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

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

注本題為2005年四川預賽題，事實上此題源自2003年全國高考理科試卷壓

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

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

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

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

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

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

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

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

第19頁共82頁

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

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

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

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

%τ=28個.

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

n—65,5〃=325.

5

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

k=?

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

61000,60100,60010,60001,52000.

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

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

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

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

^n-?_「"I

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

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

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

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

數(shù).

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

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

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

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

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

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

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

第20頁共82頁

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

a=2

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

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

力的取值1234^5^6789

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

數(shù)

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

16x4=64個.

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

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

16x6=96個.

以上共計144+64+96=304個.

(3)當數(shù)碼組恰含三個值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

個.

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

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

式,于是這種〃有34x12=408個.

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

以上共計168+408+408=984個〃值.

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

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

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