組合數(shù)學習題解答

1、第一章：1.2. 求在1000和9999之間各位數(shù)字都不相同，而且由奇數(shù)構成的整數(shù)個數(shù)。解：由奇數(shù)構成的4位數(shù)只能是由1，3，5，7，9這5個數(shù)字構成，又要求各位數(shù)字都不相同，因此這是一組從5個不同元素中選4個的排列，所以，所求個數(shù)為：P(5,4)=120。 1.4. 10個人坐在一排看戲有多少種就坐方式？如果其中有兩人不愿坐在一起，問有多少種就坐方式？解：這顯然是一組10個人的全排列問題，故共有10！種就坐方式。如果兩個人坐在一起，則可把這兩個人捆綁在一起，如是問題就變成9個人的全排列，共有9！種就坐方式。而這兩個人相捆綁的方式又有2種（甲在乙的左面或右面）。故兩人坐在一起的方式數(shù)共有2*9

2、！，于是兩人不坐在一 起的方式共有 10！- 2*9！。1.5. 10個人圍圓桌而坐，其中兩人不愿坐在一起，問有多少種就坐方式？解：這是一組圓排列問題，10個人圍圓就坐共有 種方式。兩人坐在一起的方式數(shù)為,故兩人不坐在一起的方式數(shù)為：9！-2*8！。1.14. 求1到10000中，有多少正數(shù)，它的數(shù)字之和等于5？又有多少數(shù)字之和小于5的整數(shù)？解：(1)在1到9999中考慮，不是4位數(shù)的整數(shù)前面補足0，例如235寫成0235,則問題就變?yōu)榍螅簒1+x2+x3+x4=5 的非負整數(shù)解的個數(shù)，故有F（4，5）56(2)分為求：x1+x2+x3+x4=4 的非負整數(shù)解，其個數(shù)為F（4，4）=35x1+

3、x2+x3+x4=3 的非負整數(shù)解，其個數(shù)為F（4，3）=20x1+x2+x3+x4=2 的非負整數(shù)解，其個數(shù)為F（4，2）=10x1+x2+x3+x4=1 的非負整數(shù)解，其個數(shù)為F（4，1）=4x1+x2+x3+x4=0 的非負整數(shù)解，其個數(shù)為F（4，0）=1將它們相加即得，F(xiàn)（4，4）+F（4，3）+F（4，2）+F（4，1）+F（4，0）=70。第二章：2.3. 在邊長為1的正三角形內(nèi)任意放置5個點，則其中至少有兩個點的距離1/2。解：將邊為1的正三角形分成邊是為1/2的四個小正三角形，將5個點放入四個小正三角形中，由鴿籠原理知，至少有一個小正三角形中放有2個點，而這兩點的距離1/2。

4、1/2 1/2 1/22.5. 在圖中，每個方格著紅色或藍色，證明至少存在兩列有相同的著色。解：每列著色的方式只可能有種，現(xiàn)有列，由鴿籠原理知，至少有二列著色方式相同。 ï2.7. 一個學生打算用37天總共60學時自學一本書，他計劃每天至少自學1學時，證明：無論他怎樣按排自學時間表，必然存在相繼的若干天，在這些天內(nèi)其自學總時數(shù)恰好為13學時。解：設是第一天自學的時數(shù)，是第一，二天自學的時數(shù)的和，是第一，二， ，第天自學時數(shù)的和，于是，序列是嚴格遞增序列(每天至少一學時)，而且， 于是序列也是嚴格遞增的序列，故因此74個數(shù)都在1和73兩個整數(shù)之間，由鴿籠原理知，這74個數(shù)中必有兩個是相

5、等的，由于中任何兩數(shù)都不相等，故中任何兩個數(shù)也是不相等的，因此，一定存在兩個數(shù)使得因此，在這些天中，這個學生自學總時數(shù)恰好為13。 ï2.10. 證明：在任意52個整數(shù)中，必存在兩個數(shù)，其和或差能被100整除。證明：設52個整數(shù)a1，a2，.，a52被100除的余數(shù)分別為r1，r2，.，r52,而任意一整數(shù)被100除可能的余數(shù)為0，1，2，.,99，共100個，它可分為51個類：0，1，99，2，98，.49，51，50。因此，將51個類看做鴿子籠，則由鴿籠原理知，將r1，r2，.，r52 個鴿子放入51個籠中，至少有兩個屬于同一類，例如ri,rj,于是ri=rj或ri+rj=100

6、,這就是說aiaj 可100整除，或ai + aj 可被100整除。第三章3.2. 求1到1000中既非完全平方又非完全立方的整數(shù)個數(shù)。解：設1,2,1000;表示1到1000中完全平方數(shù)的集合，則表示1到1000中不是完全平方數(shù)的集合；表示1到1000中完全立方數(shù)的集合，則表示1到1000中不是完全立方數(shù)的集合。故表示1到1000中既非完全平方又非完全立方的整數(shù)的集合，由容斥原理（3.5）式）知：(3.5)其中1000，,表示1到1000中既是完全平方又是完全立方的數(shù)的集合，故=3,將以上數(shù)值代入(3.5)式得1000(31+10)+3=962 故1到1000中既非完全平方又非完全立方的整數(shù)

7、個數(shù)為962。 3.8. 在所有的n位數(shù)中，包含數(shù)字3，8，9但不包含數(shù)字0，4的數(shù)有多少？解：除去0，4，則在1，2，3，5，6，7，8，9這8個數(shù)字組成的n位數(shù)中，令S表示由這8個數(shù)字組成的所有n位數(shù)的集合。則|S|=8n.P1表示這樣的性質(zhì)：一個n位數(shù)不包含3；P2表示這樣的性質(zhì)：一個n位數(shù)不包含8；P3表示這樣的性質(zhì)：一個n位數(shù)不包含9；并令Ai表示S中具有性質(zhì)Pi的元素構成的集合（i=1,2,3）。則表示S中包含3，又包含8，又包含9的所有n位數(shù)的集合。由容斥原理（3.5）式）得 |= （3.5）而，代入（3.5）式得 故所求的n位數(shù)有個。3.10. 求重集的10-組合數(shù)。解：構造集

8、合B=。令集合B的所有10-組合構成的集合為S。由第一章的重復組合公式(1.11)有F（3，10）=66。令p1表示S中的元素至少含有4個a這一性質(zhì)，令p2表示S中的元素至少含有5個b這一性質(zhì)，令p3表示S中的元素至少含有6個c這一性質(zhì)，并令Ai(i=1,2,3)表示S中具有性質(zhì)pi(i=1,2,3)的元素所構成的集合，于是B的10-組合數(shù)就是S中不具有性質(zhì)p1,p2,p3的元素個數(shù)。由容斥原理（3.5）式）有：|= (3.5)由于已經(jīng)求得=66，下面分別計算(3.9)式右端其他的項。由于A1中的每一個10-組合至少含有4個a，故將每一個這樣的組合去掉4個a就得到集合B的一個6-組合。反之，如

9、果取B的一個6-組合并加4個a進去，就得到了A1的一個10-組合。于是A1的10-組合數(shù)就等于B的6-組合數(shù)。故有=F（3，6）28同樣的分析可得=F（3，5）21=F（3，4）15用類似的分析方法可分別求得F（3，1）3F（3，0）10（因為5611>10）0 （同上）將以上數(shù)值代人(3.9)式得到：|66（282115）（310）06故所求的10-組合數(shù)為6。 3.14. 求由數(shù)字1，2，8所組成的全排列中，恰有4個數(shù)字在其自然位置上的全排列個數(shù)。解：4個數(shù)在其自然位置共有種方式，對某一種方式，均有4個數(shù)字不在其自然位置，這正好是一個錯排，其方式數(shù)為（見定理3.2），由乘法規(guī)則有，恰

10、有4個數(shù)字在其自然位置上的全排列數(shù)為630。 第四章4.6 求重集的10-組合數(shù)。解：設重集B的n-組合數(shù)為，則序列的普通母函數(shù)為 =(1-x4-x6-x8+x10+x12+x14-x18)所以a10= =286-84-35-10+1=158故重集B的10組合數(shù)為158。4.9. 設重集,并設是滿足以下條件的r-組合數(shù)，求序列的普通母函數(shù)。a. 每個 出現(xiàn)3的倍數(shù)次。b. ,至多出現(xiàn)1次，至少出現(xiàn)2次，最多出現(xiàn)4次。c. 出現(xiàn)偶數(shù)次，出現(xiàn)奇數(shù)次，出現(xiàn)3的倍數(shù)次，出現(xiàn)5的倍數(shù)次。d. 每個至多出現(xiàn)8次。解：a. b. c. d. 4.10 有兩顆骰子，每個骰子六個面上刻有1，2，3，4，5，6個

11、點。問擲骰子后，點數(shù)之和為，兩顆骰子的點數(shù)有多少種搭配方式？解：每個骰子是不同的，但討論點數(shù)之和的時候不考慮順序，故該問題是組合問題。設有滿足條件的搭配方式有種，則其普通母函數(shù)為 其中的系數(shù)即為所求的搭配方式數(shù)。4.14 求由數(shù)字2，3，4，5，6，7組成的位數(shù)中，3和5都出現(xiàn)偶數(shù)次，2和4至少出現(xiàn)一次的位數(shù)的個數(shù)。解：這是一個排列問題。設滿足條件的位數(shù)的個數(shù)為，則序列對應的指數(shù)母函數(shù)為： =所以，5.2. 如果用an表示沒有兩個0相鄰的n位三元序列（即由0，1，2組成的序列）的個數(shù)。求an所滿足的遞歸關系并解之。 解：對n位三元序列的第一位數(shù)有三種選擇方式:1)第一位選1，則在剩下的n-1位

12、數(shù)中無兩個0相鄰的個數(shù)為an-1;2)第一位選2，則在剩下的n-1位數(shù)中無兩個0相鄰的個數(shù)為an-1; 3)第一位選0,則在第二位又有兩種選擇方式： (1)第二位選1，則在剩下的n-2位數(shù)中無兩個0相鄰的個數(shù)為an-2； (2)第二位選2，則在剩下的n-2位數(shù)中無兩個0相鄰的個數(shù)為an-2顯然有a1=3,a2=8 由加法規(guī)則得an所滿足的遞歸關系為：其特征方程為x2-2x-2=0 特征根為x1=1+,x2=1-由定理5.3知其通解為an=c1(1+)n+c2(1-)n由初始條件有 解以上方程組得 ， 5.4. 某人有n元錢，她每天要去菜市場買一次菜，每次買菜的品種很單調(diào)，或者買一元錢的蔬菜，或

13、者買兩元錢的豬肉，或者買兩元錢的魚。問，她有多少種不同的方式花完這n元錢?解：設花完這n元錢的方式有an種，則第一次花錢可分為下面幾種情況： 1)若第一次買一元錢的菜，則花完剩下的n-1元錢就有an-1種方式， 2)若第一次買二元錢的肉，則花完剩下的n-2元錢就有an-2種方式， 3)若第一次買二元錢的魚，則花完剩下的n-2元錢就有an-2種方式，顯然有a1=1，a2=3. 由加法規(guī)則,得遞歸關系如下： 其特征方程為：特征根.通解 .由初始條件得解得.故該遞歸關系的解為 故她有種不同的方式花完這n元錢。5.6求解下列遞歸關系a解：這是一個常系數(shù)線性非齊次遞歸關系式，其導出的齊次遞歸關系為：其特

14、征方程為， 解得 由定理5.3知，所導出的齊次線性遞歸關系的通解為由于f(n) =3, 且1不是式遞歸關系式的特征根，故設特解為將代入遞歸關系得 由定理5.6知，遞歸關系式的通解為 將初值條件代入上式并解得故 。b解：這也是一個常系數(shù)線性非齊次遞歸關系式，其導出的齊次遞歸關系的特征方程為特征根為由定理5.3知，所導出的齊次線性遞歸關系的通解為由于f(n) =3n,且1不是遞歸關系式的特征根，故設特解為將上式代入遞歸關系式解得 通解由初始條件有 解得故遞歸關系的解為： c.解：對應齊次遞歸關系的特征方程為x2-7x+10=0其特征根x1=5,x2=2 又f(n)=3n, 且3不是遞歸關系式的特征根，故設特解為，將 代入原遞歸關系得解得A=通解為由初始條件有解出c1=11/6,c2=8/3故原遞歸關系的解為： d.解：對應齊次遞歸關系的特征方程為x2+5x+6=0解得x1=-2,x2=-3。齊次遞歸關系的通解為：又f(n)=42, 且4不是遞歸關系式的特征根，故設特解為 ,將代入遞歸關系得A4n+5A4n-1+6A4n-2=42×4n解得A=16,故通解為an=ac1(2)n+c2(3)n+16×4n由初始條