李凡長版 組合數(shù)學(xué)課后習(xí)題答案 習(xí)題2

1、第二章 容斥原理與鴿巢原理1、1到 10000之間（不含兩端）不能被 4，5和 7整除的整數(shù)有多少個？解 令A(yù)=1,2,3,10000，則 |A|=10000.記A 、A 、A 1與1000之間能被4,5和7整除的整數(shù)集合，則有：123|A | =L10000/4=2500,1|A | =L10000/5=2000,2|A | =L10000/7=1428,3于是A A 表示中能被4和5整除的數(shù),即能被20 整除的數(shù)，其個數(shù)為12| A A L10000/20=500；12同理，| A A L10000/28=357,13| A A L10000/35=285,23A A A 表示中能同時被4

2、,5,7中能被4,5,7的最小公倍123數(shù)lcm(4,5,6)=140整除的數(shù)，其個數(shù)為| A A A L10000/140= 71.123由容斥原理知，中不能被4，5，7整除的整數(shù)個數(shù)為| A A A |123= |A| - (|A | + |A | +|A |) + (|A A | + |A A | +|A A |) - |A A A |123121332123= 51432、1到 10000之間（不含兩端）不能被 4或 5或 7整除的整數(shù)有多少個？解 令A(yù)=1,2,3,10000A A A 1與1000之間能被4,5和7整除123的整數(shù)集合，中不能被4，5，7整除的整數(shù)個數(shù)為= |A|

3、- - 2 = 10000 -L10000/140- 2 = 9927| A A A | A A A |1231233、1到 10000之間（不含兩端）能被 4和 5整除，但不能被 7整除的整數(shù)有多少個？解 令A(yù) 表示在1與10000之間能被4和5整除的整數(shù)集，A 表示4和 5 整除，12也能被 7 整除的整數(shù)集。則：|A | =L10000/20= 500,1|A | =L10000/140= 71,2所以 1 與 10000 之間能被 4 和 5 整除但不能被 7 整除的整數(shù)的個數(shù)為：500-71=429。4、計(jì)算集合2a,3b, 2c, 4d的 5組合數(shù). 解 令S a, b,c,d，則

4、S的5組合數(shù)為= 565415設(shè)集合是S 的5565組合中的的個數(shù)小于等于2b的個數(shù)小于等于3的個數(shù)小于等于2d的個數(shù)小于等于4的組合數(shù). 定義性質(zhì)集合P=P ,P ,P ,P ,其中：1234P ：5組合中的個數(shù)大于等于3；1P ：5組合中b的個數(shù)大于等于4；2P ：5組合中c的個數(shù)大于等于3；3P ：5組合中d的個數(shù)大于等于5.4將滿足性質(zhì)P的5A(1i4). 那么，A 中的元素可以看作是由i1i S 的5323個a構(gòu)成的，所以|A | = 10.2411210類似地，有 |A | = 4. |A | = 10. |A | = 1.544153415541231545355 |A A |

5、= 0.5344153412| A A | = | A A | = | A A | = | A A | = | A A | = | A A A |1314242334124= | A A A | = | A A A | =| A A A A | = 01233241234而的個數(shù)小于等于2b的個數(shù)小于等于3的個數(shù)小于等于2d的個數(shù)小于等于4的5組合全體為 ，由容斥原理知，它的元素個數(shù)為| A A A A |123456-(10+4+10+1)-(0+0+0+0+0+0)+(0+0+0)-0=31。5、計(jì)算a,3b, 10c的 10 組合數(shù). 解 令S a, b,c，則S的10組合數(shù)為= 661

6、031設(shè)集合是S 的106610組合中的b的個數(shù)小于等于3，的個數(shù)小于等于10的組合數(shù). 定義性質(zhì)集合P= P ,P ,其中：12P ：10組合中b的個數(shù)大于等于4；1P ：10組合中c的個數(shù)大于等于11；2 將滿足性質(zhì)P的10A (1i4). 那么， |A | = 28.10431104i1i 類似地，有 |A | =故由容斥原理知，所求組合數(shù)為= 0. |A A | = = 0.10312121066-(28+0)-0 。6、求集合ax, by, cz的 m 組合數(shù)（a,b,c全非無窮大）.解 用上面的方法可以得出該集合的m 組合數(shù)為： 3m13ma13mb13mc1 mra1rb1rc1

7、3mab213mbc21rbc23mca21rca23mcab31rcab3 rab22mmma1mb12mc1 22mab2macmcb2mabc1227、某班學(xué)生 25 人可以選修二外，其中有 14 人選修日語，12 人選修法語，5 人選修日語和德語，6 人選修法語和日語，2 人選修這 3 6 個選修德語的都選了另一種外語（這 3 解 設(shè)選修日語，法語，德語的學(xué)生集合分別為J，則|J| = ，|F| = ，|G| = 6，J| = ，J| = 5，JG| = ，G| =6-5+23。故沒有選修的人數(shù)為：|FG J| = 25 (12 + 14 + 6) + (6+5+3) 2 = 5。8、

8、1 到 120 的整數(shù)中有多少質(zhì)數(shù)？多少合數(shù)？解 a為合數(shù)，p為ap ，a故不超過 120 的合數(shù)必定是 2，3，5，7 的倍數(shù)。根據(jù)容斥原理可得，合數(shù)的個數(shù)為 89，質(zhì)數(shù)為 119-89 = 。119、求方程 x + x + x = 10的大于 2 的整數(shù)解的個數(shù).123解 相當(dāng)于求 S=a, b,c的 10-2*34 組合數(shù)的個數(shù)。 15431410、 求方程 x + x + x + x = 18 的非負(fù)整數(shù)解的個數(shù)，其中 0 x 5, 0 x1234126, 5x 9, 2x 10.34提示 令 y = x y =x y =x y = x 5x ,6x ,4x ,8x 的 11組合數(shù)。1

9、1223344123411、 一花店某時只有 6 枝紅玫瑰，7 枝粉玫瑰和 8 枝黃玫瑰。這時要從中選12 枝做花籃，問有多少種選法？提示 相當(dāng)于求S=6a, 7b,8c 的 12 組合數(shù)的個數(shù)。12、 某人要給 5 個朋友每人一件生日禮物，問禮物全部送錯的概率是多少？解 D = 5!513、 對集合1,2,10 5 個元素在其自然位置上的排列有多少種？.解 任意選出 5 個元素放在其自然位置上，其余的全部錯排： D5514、 說明組合恒等式 n! D D Dnn0n1n1n0的組合意義.（設(shè) D = ）0解 S=1,2,n排列可分成下列情況：沒有一個數(shù)在其自然位置上的排列數(shù)為 D 。nn0恰

10、有 i（i=1,2,n）個數(shù)在其自然位置上的排列數(shù)為 D 。nn-iiS 的所有排列的個數(shù)為 。根據(jù)加法原理，有： nn! =D +D +Dnnnn-1001n15、 計(jì)算機(jī)接到 n 個用戶的信號，每個信號都由一個 A 類數(shù)據(jù)加一個 B 類數(shù) n 個用戶每人一個 A 類數(shù)據(jù)和一個 B 類數(shù)據(jù)。那么沒有人接到的數(shù)據(jù)與他發(fā)出的相同的概率是多少？解 如果發(fā)給用戶的 A類數(shù)據(jù)全排列，B類錯排：n!Dn如果發(fā)給用戶的 B類數(shù)據(jù)全排列，A類錯排：n!Dn如果發(fā)給用戶的 A類、B類數(shù)據(jù)全部錯排：D2n則沒有人接到的數(shù)據(jù)與他發(fā)出的相同的方案數(shù)為：n!D + n!D - D 。nnn所求概率為：(2* n!D

11、- D )/( ) 。2nn16、 把 20 個相同的球放入 5 2 個盒子每個最多可以放6 個球。問共有多少種不同的方法？ 6解i21 20ii20ii017、 10 個人在舞會中跳舞。問有多少種方法？若在第二支舞曲中，每個人都12換了舞伴呢？解 從原來的每一對舞伴種選出一個，讓這5 個人錯排：2 D 。5518、 證明：n 對夫妻圍坐于一圓桌旁，假定 n 位妻子 w ,w ,w 先坐好，將12n丈夫們 h ,h ,h r對夫妻相鄰而坐的方案數(shù)為12n 2n2nkM(n,r)n()kr(nkk2nkrkkr證明 設(shè) N是 h ,h ,h 的所有排列的集合12n令 A ：h 坐在 w 右邊的排

12、列；111A ：h 坐在 w 左邊的排列；211A ：h 坐在 w 右邊的排列；322A ：h 坐在 w 左邊的排列；422A ：h 坐在 w 左邊的排列；2n-1nnA ：h 坐在 w 左邊的排列。2nnn注意：A 和 A 不可能同時成立i=1,2,2n。ii+1若依序?qū)?A ，A ，A 沿一圓周排列，則 |AA | = 0 （i=1,2,2n）122nii+1假如沿圓周有兩個相鄰時，則0。A A . AA ,A ,.,Aiiiiii12k12k總之：（1） 對于整數(shù) k，0。亦即A A . Aiii12ka(k) =0。A A . Ai1ii2ki i i 2n12k（2） 對于 1kn，

13、根據(jù) n 對夫妻問題，有 2na(k) =(nk)!。A A . A2 1n kk1iiik12ki i i 2n12k由容斥原理有：M(n,r)2nr(a(k)kr krkr 2nn(kr(nk)!k2nk1r k k1kr 2n2nkn()kr(nkk2nkrkkr19、 A,B,C,D,E 五位學(xué)生選課，共有a,b,c,d,e 五門課可選。由于基礎(chǔ)不同，A 不可以選 a 和 cB 不可以選 bC 不可以選 c,d 和 eD 不可以選 a,b 和 c，E 可以選任何課。如果每人選一門，共有多少種選法？每人選兩門呢？解 令 S 為每人選一門的所有選法集合，則|S| = 5 .5定義性質(zhì)集合P

14、=P ,P ,P ,P ,其中：1234P ：選或；1P ：選b；2P ：C選，d或；3P ：選，b或。4設(shè)S為SPi，所以ii13|A | = 2*5 ； |A | = 1*5 ； |A | = 3*5 ；|A | =3*5 。44441234|A A | = 2*1*5 ；|A A | = 3*1*5 ；|A A | = 2*3*5 ；|A A | = 2*3*5 ；|A A | = 3*1*5 ；|A A | = 3*3*5 。|A A A | = 2*1*3*5 ；|A A A | = 2*1*3*5 ；|A A A | = 2*3*3*5 ；|A A A | = 1*3*3*5 。3

15、331232133331442342212312422134234|A A A A | = 2*1*3*3*5 ；1123因此，滿足題意的排列數(shù)為：4| A A A A |1234= |A|-(|A |+ |A |+ |A | + |A )+(|A A | + |A A | + |A A |1234123213+ |A A | +|A A | + |A A )-(|A A A | + |A A A |142434123234+ |A A A | +|A A A |) +|A A A A |同理可做每人選兩門的124134123420、 一個班共有 10個女生和 10個男生，那么至少要叫出多少人

16、，才能保證叫出的人中有一個女生？解 11人21、 證明：從 1至 2n的 2n個自然數(shù)中任選 n+1個，那么其中至少有一對數(shù)互質(zhì).證明 首先證明：任何兩個相鄰的正整數(shù)是互質(zhì)的。用反證法：假設(shè) n 與 n+1有公因子 q（q2n=qp ,n+1=qp ,p ,p 是整數(shù)。1212因此 qp +1= qp ，即 q (p p 。這與 q，p p 是整數(shù)矛盾。因此，任何兩個相鄰的正整數(shù)是互質(zhì)的。122121現(xiàn)把 1,2,2n 分成以下 n 組：1,2,3,4,2n-1,2n，從中任取 n+1 個不同的數(shù)。由鴿巢原理可知：至少有兩個數(shù)取自同一組。它們是互質(zhì)的。得證。22、 52100整除.證明 設(shè) 5

17、2 個整數(shù) a ,a ,a 被 100 整除的余數(shù)分別是r ,r ,r 。另外，可能1 2521 252的余數(shù)共 100 個：0199 51 類01,992,9849,51，50。因此 r(0i53)中至少有兩個屬于同一類，例如 r,r 。于是或者 r=r ，ij kjk或者 r+r =100。這就是說，它們的和或者差可被 100 整除。jk23、 西方風(fēng)俗中，如果13日是星期五，會被認(rèn)為是不祥的日子，被稱作“黑色星期五”.試證明：非閏年時每年都至少有一個“黑色星期五”.證明 每年中共有 12 個 13 日，它們分別是(下面用 m.n 表示 m 月 n 日，wx 星期 x)1.13，2.13，

18、。下面用反證法來證明。假設(shè)它們均非星期 5，則它們是 w1，w2，w3，w4，w6w7之一。我們知道2.133.13 和 11.13必是同一個 wx （因?yàn)樗鼈冎g1分別相隔 28 天及 245 1.13 和 10.13 是同一個 wx 而且 x x ；2124.13 與 7.13 同為 x 9.13與 12.13 同為 x（所有xx 3 個 1334ij日是剩下的兩個 wx 和 wx 。根據(jù)鴿巢原理，這 3 日中至少有兩個是屬于同56一個 wx 的，而實(shí)際情況是它們間相隔天數(shù)都不是 7 的整數(shù)被。因此原假設(shè)14xy324、 證明：任意 7個實(shí)數(shù)中必存在兩個實(shí)數(shù) x，y，滿足 01xy 3x

19、y證明 令x = tan , y = tan ，則= tan( )。1 3若 0 /6，則 0tan( )。3這 7 7 4 tan , y = tan , tan , tan ，0 , , , /2。將它們分布于0, /6, /6, /3, /3, /2之中，則必有兩個屬于同一區(qū)間。設(shè) , 屬于同一區(qū)間且 0 - ，則 0 /6。得證。25、 在一次會議中，有 5位聽眾每人均離開兩次，而且每兩人均有同時離開的時刻。證明：一定有三人同時離開的時刻.證明 5 人中人一位，設(shè)為，按題意，共離開兩次；在這兩次中，其余4 人都離開過，按照鴿巢原理，這 4 人中必然至少有兩人是同時離開的。即，必然有三人同時離開的時刻。得證。26、 設(shè) a ,a ,a 是 1,2,n 的一個排列.試證明：當(dāng) n為奇數(shù)時，(a -1)(a1 2n12（a n)是偶數(shù).nn12證明 當(dāng) n 是奇數(shù)時，1，2，n 和 a ,a ,a 中的奇數(shù)是個，而偶數(shù)只1 2nn1n1有個。因此在a a ，a 1 中 a ,a ,a （共個）至少有113n1 3n22個是奇數(shù)，例如 a 是奇數(shù)，則 a-1是偶數(shù)。于是可知整個乘積是偶數(shù)。ii27、 9 個頂點(diǎn)的完全圖 K 9個紅色 K ，或者存在一個藍(lán)色 K .43證明 在 K 中如果與每個頂點(diǎn)關(guān)