《组合数学》姜建国著(第二版)-课后习题答案完全版

《组合数学》练习题一参考答案《组合数学》练习题一参考答案一、填空：1.!()!m n P n m m n m =- 2.2)1(-n n 3. 0. 4. 2675.),2,1,0(3)2(2321 =+-+=n c c c a n n n n .6.4207.78.()()!!11...!31!21!111n n n ??-++-+-9.22 10.267二、选择：1. 1—10 A B D D A D A B B C三、计算： 1. 解因为]250[=25, ]450[=12, ]850[=6, ]1650[=3, ]3250[=1, ]6450[=0, 所以, 所求的最高次幂是2(50!)=25+12+6+3+1=47.2. 解由我们最初观察的式子,有614,1124,634,144=??===, 再利用定理1,我们得到24!415,102)15(545,155==??=-?==, 3511642434435=+?=???+=, 5061141424425=+?=??+=. 所以,x x x x x x f 24503510)(23455+-+-=.3. 解：设所求为N ，令}2000,,2,1{ =S ，以A ，B ，C 分别表示S 中能被32?，52?，53?整除的整数所成之集，则53466663133200333 532200053220003532000522000322000 =+?-++=+-???????+???????+???????=+---++==C B A C B C A B A C B A CB A N 4. 解：记7个来宾为1A ，2A ，…，7A ，则7个来宾的取帽子方法可看成是由1A ，2A ，…，7A 作成的这样的全排列：如果i A （1≤i ≤7）拿了j A 的帽子，则把i A 排在第j 位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数7D ，即等于1854。

4.1 证明所有的循环群是 ABEL 群 证明：
循环群也是群，所以群的定义不用再证，只需证明对于任意a, b G, G是循环群，有a * b b * a成立，因为循环群中的元素可写成a=xm 形式 所以等式左边xm × x n x m n , 等式右边x n xm＝x m n， a b b a，即所有 的循环群都是ABEL群。
因为 H 是 G 的子群， 所以在 H 中的一个 (b m ) r 一定在 G 中对应一个 a m 使得
(b m ) r a m ，
所以有 b rm a m ，则 rm 一定是 m 的倍数，所以则 H 的阶必除尽 G 的阶。 4．9 G 是有限群，x 是 G 的元素，则 x 的阶必除尽 G 的阶。
N-1 N-2
N
1
2 3
……
……
图N! C N!
如图： N 个人围成一个圆桌的所有排列如上图所示。一共 N!个。
……
…
6
…………………………
… …
……
… …
…
…
旋转 360/i，i={n,n-1,n-2,……1}； 得到 n 种置换 当且仅当 i=1 的置换（即顺时针旋转 360/1 度：P1=(c1)(c2)……(cn!);） 时有 1 阶循环存在 （因为只要圆桌转动，所有圆排列中元素的绝对位置都发生了 变化，所以不可能有 1 阶循环存在） 。 不同的等价类个数就是不同的圆排列个数，根据 Burnside 引理，
4.18 若以给两个 r 色球，量个 b 色的球，用它装在正六面体的顶点，试问有多 少种不同的方案。 解：单位元素（1） （2） （3） （4） （5） （6） （7） （8） ，格式为（1）8. 绕中轴旋转 90。的置换非别为（1234） （5678） ， （4321） （8765） 2 格式为（4） ，同格式的共轭类有 6 个。

习题四（容斥原理）1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则22001002A ⎢⎥==⎢⎥⎣⎦，3200663A ⎢⎥==⎢⎥⎣⎦，5200405A ⎢⎥==⎢⎥⎣⎦，7200287A ⎢⎥==⎢⎥⎣⎦， 112001811A ⎢⎥==⎢⎥⎣⎦，132001513A ⎢⎥==⎢⎥⎣⎦，232003323A A ⎢⎥==⎢⎥⨯⎣⎦， 252002025A A ⎢⎥==⎢⎥⨯⎣⎦，272001427A A ⎢⎥==⎢⎥⨯⎣⎦，2112009211A A ⎢⎥==⎢⎥⨯⎣⎦， 2132007213A A ⎢⎥==⎢⎥⨯⎣⎦，352001335A A ⎢⎥==⎢⎥⨯⎣⎦，37200937A A ⎢⎥==⎢⎥⨯⎣⎦， 3112006311A A ⎢⎥==⎢⎥⨯⎣⎦，3132005313A A ⎢⎥==⎢⎥⨯⎣⎦，57200557A A ⎢⎥==⎢⎥⨯⎣⎦， 5112003511A A ⎢⎥==⎢⎥⨯⎣⎦，5132003513A A ⎢⎥==⎢⎥⨯⎣⎦，7112002711A A ⎢⎥==⎢⎥⨯⎣⎦， 7132002713A A ⎢⎥==⎢⎥⨯⎣⎦，111320011113A A ⎢⎥==⎢⎥⨯⎣⎦，2352006235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 2372004237A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231120032311A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231320022313A A A ⎢⎥==⎢⎥⨯⨯⎣⎦ 2572002257A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251120012511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251320012513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 271120012711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，271320012713A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 21113200021113A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，3572001357A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，351120013511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦351320013513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，371120003711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，…， 235720002357A A A A ⎢⎥==⎢⎥⨯⨯⨯⎣⎦，…，23571113200023571113A A A A A A ⎢⎥==⎢⎥⨯⨯⨯⨯⨯⎣⎦， 所以 23571113200(1006640281815)(3320149713965533221)(6432211110111i i j i j k i j k lii ji j ki j k li j k l m i j k l m ni j k l mi j k l m nA A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+-+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑∑0)00041+-+=但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：416146+-=2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，则2200010002A ⎢⎥==⎢⎥⎣⎦，320006663A ⎢⎥==⎢⎥⎣⎦，520004005A ⎢⎥==⎢⎥⎣⎦， 23200033323A A ⎢⎥==⎢⎥⨯⎣⎦，25200020025A A ⎢⎥==⎢⎥⨯⎣⎦，35200013335A A ⎢⎥==⎢⎥⨯⎣⎦， 235200066235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， （1）即求235A A A ++，根据容斥原理有：235235232535235()1000666400(333200133)661466A A A A A A A A A A A A A A A ++=++-+++=++-+++=（2）即求232535A A A A A A ++，根据容斥原理有：232535232535235235235235()333200133266534A A A A A A A A A A A A A A A A A A A A A A A A ++=++-+++=++-⨯=（3）即求[1]N ，根据Jordan 公式有：1112233235232535235[1]2()310006664002(333200133)366932N q C q C q A A A A A A A A A A A A =-+=++-⨯+++⨯=++-⨯+++⨯=3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。

第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 2⨯5⨯P(8,2)+3⨯4⨯P(8,2)6. (n+1)!-17. 用数学归纳法易证。

8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn k , 则n 2的除数个数为 ( 2p 1+1) (2p 2+1) …(2p k+1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。

11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。

当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。

故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。

组合数学(第2版)-姜建国,岳建国习题一（排列与组合）1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？ 解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数；（1）选1个，即构成1位数，共有15P 个；（2）选2个，即构成两位数，共有25P 个；（3）选3个，即构成3位数，共有35P 个；（4）选4个，即构成4位数，共有45P 个；由加法法则可知，所求的整数共有：12345555205P P P P +++=个。

2．比5400小并具有下列性质的正整数有多少个？（1）每位的数字全不同；（2）每位数字不同且不出现数字2与7；解：（1）比5400小且每位数字全不同的正整数；按正整数的位数可分为以下几种情况：① 一位数，可从1～9中任取一个，共有9个；② 两位数。

十位上的数可从1～9中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有9981⨯=个；③ 三位数。

百位上的数可从1～9中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有299648P ⨯=个；④ 四位数。

又可分三种情况：⏹ 千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有3942016P ⨯=个；⏹ 千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩下的8个数字中选2个进行排列，共有283168P ⨯=个；⏹ 千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有2856P =个；根据加法法则，满足条件的正整数共有：9816482016168562978+++++=个；（2）比5400小且每位数字不同且不出现数字2与7的正整数；按正整数的位数可分为以下几种情况：设{0,1,3,4,5,6,8,9}A =① 一位数，可从{0}A -中任取一个，共有7个；② 两位数。

十位上的数可从{0}A -中选取，个位数上的数可从A 中其余7个数字中选取，根据乘法法则，共有7749⨯=个；③ 三位数。

3.1 某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议?解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28甲参加的会议数为 28+5=333.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。

解：设 A 3：被3整除的数的集合A 5：被5整除的数的集合 A 7：被7整除的数的集合 所以 ||=||-||=-=33-4=29 3.3 n 个代表参加会议，试证其中至少有2个人各自的朋友数相等解：每个人的朋友数只能取0，1，…，n －1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n －2．故这n 个人的朋友数的实际取数只 有n －1种可能．，根据鸽巢原理所以至少有２人的朋友数相等．3.4试给出下列等式的组合意义0j j 0(1)=(1), 1n-m-j+1(2)(1)1 j 1(3)...(1) 1 12m l l n m l n m m n l n k m n k l k l n m l n m l m l m l m l m l m l m m m m m l =-=--⎛⎫⎛⎫⎛⎫-≥≥ ⎪ ⎪⎪-⎝⎭⎝⎭⎝⎭---⎛⎫⎛⎫⎛⎫=- ⎪ ⎪⎪--⎝⎭⎝⎭⎝⎭+-++++⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫=-+-+- ⎪ ⎪ ⎪ ⎪ ⎪-+++⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭∑∑ 证明：（1）从n 个不同元素中取k ，使得其中必含有m 个特定元素的方案数为)()(kn mn m k mn --=--。

设这m 个元素为a 1,a 2,…,a m , Ai 为包含a i 的组合（子集），i=1,…,m.1212|...|(...)12 =(...(1))1 2 =(1) m m m l n A A A A A A k n m n m n m n m k k k m k m n l l k ⎛⎫=- ⎪⎝⎭---⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭-⎛⎫⎛- ⎪⎝⎭ 0ml =⎫ ⎪⎝⎭∑ （2）把l 个无区别的球放到n 个不同的盒子，但有m 个空盒子的方案数为11n l m n m -⎛⎫⎛⎫⎪⎪--⎝⎭⎝⎭令k=n-m ，设A i 为第i 个盒子有球，i=1，2，…k12k 121|...|(...)1k 11211 =(...(1)) 1 2 k k k l A A A A A A k k l k l k k l k k k l k l l k l +-⎛⎫=- ⎪⎝⎭+--+--+--+-⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭ kj j 0k k-j+1 =(1)j l l =-⎛⎫⎛⎫- ⎪⎪⎝⎭⎝⎭∑ （3）设A i 为m+l 个元素中去m+i 个，含特定元素a 的方案集；N i 为m+l 个元素中取m+i 个的方案数。

n0
k 0
(c)an C(n 3,3), n {0,1,2,...}
n
(b)G 2 an xn , 其中an (k 1)(n 1 k )
n0
k 0
G2 (1 2x 3x2 ... (n 1)xn ...)(1 2x 3x2 ... (n 1)xn ...)
an 1 (n 1) 2 (n) ... (k 1) (n k 1) ...
G(x) 1 23 x 1 ...(n 1)3 xn 1 ...
1 x 1 x
1 x
1 (1 23 x ...(n 1)3 xn ...) 1 x
G(x)
1 1 x
1 4x x2 (1 x)4
1 4x x2 (1 x)5
2.16 用数学归纳法证明 C(m,m),C(m+1,m),C(m+2,m),...,C(m+n,m),...的母函数为 (1-x)-m-1
按叠加原理 an 4an1 3 4n 的特解为hn4n , 代入替推关系 hn4n 4h(n 1)4n1 3 4n , h 3 一般解为: r4n 3n4n 10 5n
2.28
an
a a 3
10
n 1
n2
两边求对数
ln an 3 ln an1 10 ln an2 令bn ln an bn 3bn1 10bn2 0, 特征根为 : r1 5, r 2 2,
1 ln 4
a [3n 3( 1)n ] 0
ln a a 1[3n (1)n ]
1[3n 3( 1)n ]
14
04
a a a 1[3n ( 1)n ]
1[3n 3( 1)n ]
n
14
04

１.１ 从{}5021，，，⋅⋅⋅中找两个数{}b a ,，使其满足（1） 5||=-b a ；（2）5||≤-b a解：（1）根据5||=-b a 可得 55-=-=-b a b a 或 则有种种4545 共有90种。

（2）根据5||≤-b a 得 )50,,2,1(,55{⋅⋅⋅∈+≤≤-b a b a b则：当5≤b 时，有1=b ， 61≤≤a ， 则有 6种2=b ， 71≤≤a ， 则有7种3=b ， 81≤≤a ， 则有8种4=b ， 91≤≤a ， 则有 9种5=b ， 101≤≤a ， 则有10种 当455≤<b 时，有6=b ， 111≤≤a ， 则有 11种7=b ， 122≤≤a ， 则有 11种 . . . . . . . . .45=b ， 5040≤≤a ， 则有11种 当5045≤<b 时，有46=b ， 5041≤≤a ， 则有 10种47=b ， 5042≤≤a ， 则有 9种48=b ， 5043≤≤a ， 则有 8种49=b ， 5044≤≤a ， 则有 7种 50=b ， 5045≤≤a ， 则有 6种故：共 种520)678910(21140=+++++⨯1.2 （1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进行排列，总方案数为5！×8！（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间的8个空位种的任意5个，总方案数为7！×58P（3）应该是A 女生x 女生y 女生z B,或是B 女生x 女生y 女生z A 的形式，从5个女生中选出3人进行排列，方案为35P ，考虑A,B 可以换位，方案为2×35P ，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数2×35P ×8！1.3 m 个男生,n 个女生,排成一行,其中m,n 都是正整数,若 （a ）男生不相邻（m ≤n+1）；（b ）n 个女生形成一个整体； （c ）男生A 和女生B 排在一起； 分别讨论有多少种方案。

习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。

证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。

假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。

假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。

证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。

现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。

证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。

2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。

由鸽巢原理知，至少有2个坐标的情况相同。

又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。

因为奇数+奇数= 偶数；偶数+偶数=偶数。

因此只需找以上2个情况相同的点。

而已证明：存在至少2个坐标的情况相同。

证明成立。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。

一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。

那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

证明：在任意选取的n+2个正整数中存在两个正整数，其差或和能被2n整除。

（书上例题2.1.3）证明：对于任意一个整数，它除以2n的余数显然只有2n种情况，即：0，1，2，…，2n-2，2n-1。

当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对，
当|a-b|=0时有50对
所以总的序列数=90+98+96+94+92+50=520
1.2题（王星）
解：
（a）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：
对于第一个分界线，它有n-1种选择，对于第二个分界线只有n-2个选择，(因为分界线不能相临，如果相临它们之间就没有了球，这不合要求)，依次第r-1个分界线只有n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*…*(n-r+1)/(r-1)!=C(n-1,r-1)。
而不同标志的球的排列有
所以共有8*5！种排列。
8种排列如下两类
因为要求空盒不相邻，途中1代表球
a)1111
b)1111
在a)中剩下的一个球有四种位置
b)中剩下的一个球也有四种位置
两者合起来一共有8种
1.19题（李拂晓）
n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。
③y<x<z,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为 。
所以满足题意的x,y,z的组合数为 + + ＝ 。
由于这两种方法是等价的，故可得 。证毕。
1.24题（王卓）
A={(a,b)|a,b∈Z,0≤a≤9,0≤b≤5},
(a)求x-y平面上以A作顶点的长方形的数目。
P
C
A

第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。

满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。

满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。

1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。

将女生插入，有5!种方案。

故按乘法原理，有：7!×58C ×5!=33868800(种)方案。

(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≤n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。

方法二:=150.
现有100件产品,其中有两件是次品. 如果从中任意抽出5件,抽出的产品中至多有一件次品的概率是多少
解:无次品:;
有一件次品:
因此,概率为(+)/
有七种小球,每个小球内有1～7个星星.一次活动中,主办方随机发放礼品盒,每个盒里放两个这样的小球,那么共有多少种这样的礼品盒
解:7个夫人先坐:7!/7
第一个丈夫不坐在他夫人旁边,则有5个地方可以坐;
第二个丈夫由于可以坐在第一个丈夫旁边,故有6个地方可以坐;
……………………
第7个丈夫有11分地方可以坐.
因此:5*6*7*8*9*10*11*7!/7=1197504000.
设S = {n1·a1, n2·a2,…,nk·ak},其中n1 = 1,n2 + n3 +…+ nk = n,证明S的圆排列的个数等于:
证明:r元子集共个,于是共有个最小数.下面我们求出这些最小数之和.
如果r元子集中的最小数为k,那么除k外的r-1个数只能从{k+1,k+2,…,n}中取,有种取法,即以k为最小数的r子集有个,因此这些最小数之和为.于是平均数为.
由和有
上面两式相减得:
因此=.
用二项式定理展开(4x - 3y)8.
--------------------------------------------------------------------------------
第一章 排列组合
在小于2000的数中,有多少个正整数含有数字2
解:千位数为1或0,百位数为2的正整数个数为:2*1*10*10;
千位数为1或0,百位数不为2,十位数为2的正整数个数为:2*9*1*10;

=
8 9
−
2 3
n
+
1 9
(−2)n
18.确定长为n，不包含两个相连的0或相连的1的三进制串（即由一些0、1、2组成
的串）的个数an的递推关系，然后求出an的公式 解：根据题意可知h2 = 5,h3 =12,h4 = 29
当n ≥ 5时，对于三进制串，第一个位置不为0，
当第一个位置为1时，第二个位置为0或2，对应的三进制串分别为an−2种和an−2 + an−3种 当第一个位置为2时，第二个位置为0，1或2，此时三进制串有an−1 + an−2种 于是an满足递推关系an = an−1 +3an−2 + an−3 （n ≥ 5） 它的特征方程为x3 − x2 −3x3 −1= 0
rn +
s
=
6(r(n −1) +
s) − 9(r(n − 2) +
s) + 2n ，求得 r
=
1 2
，s
=
3 2
，则 hn
=
c1 3n
+ c2n3n
+
n 2
+
3 2
。
由初始条件 h0
= 1 ， h1
=
0
，得出 c1
=
−
1 2
， c2
=
−1 6
。故 hn
=
−
3n 2
−
n3n 2
+
n 2
+
3 2
为原问题的解。
=1 (1− x3 )4
元素e1不出现，而e2出现至多一次。 对每个ei引入一个因子，我们发现
g ( x) = (1)(1+ x)(1+ x + x2 +")(1+ x + x2 +")

8.证明 C(n,n)+C(n+1,n)+ … + C(n+m,n)=C(n+m+1,n+1). 证法一 对 m 做归纳，m=0 时，等式成立。 假设对 m-1,等式成立。 C(n,n)+C(n+1,n)+ … + C(n+m-1,n)+C(n+m,n)=C(n+m,n+1)+C(n+m,n) =C(n+m,m-1)+C(n+m,m)=C(n+m+1,n+1). 证毕。 证法二：利用第 7 题结论。设有 n+2 中颜色的球，前 n+1 种球为各色彩球，第 n+2 种为黑 球。右式为，从这 n+2 个球中取出 m 个球的方案数。左式分别为从 n+1 种球中取出 0 个、1 个……m 个彩球的方案数，即黑球分别占总数 m 个，m-1 个，m-2 个……0 个大方案数，根 据加法法则，其和等于右式。
解法二：设 a 出现了 k 次，那么所有的 a 不能相邻。在 1…n 中去 k 个不相邻的 数有 C(n-k+1,k)中取法（参见第一章-习题 27）
n − k + 1 n − k 那么我们最后的答案就是 ∑ 2 。 k k =0
注： 比较解法一、二中的答案我们知道：
n 2
...
(1 − x )n+1
1
。
假设对于 n-1，命题成立。即
∑ n −1
n −1+ k k 1 。 x = (1 − x )n
n + k k n −1+ k k n −1+ k k 1 + = 。 Gn (x ) = ∑ x x ∑ ∑ n n n n −1 x = xGn ( x ) + ( ) 1 − x n + k k 1 1 。 Gn (x ) = ∑ n x = 1 − x ⋅ (1 − x )n

第1章组合数学基础1.1绪论（一）背景起源：数学游戏幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。

这样的n阶方阵称为n阶幻方。

每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。

关心的问题（1）存在性问题：即n阶幻方是否存在？（2）计数问题：如果存在，对某个确定的n，这样的幻方有多少种？（3）构造问题：即枚举问题，亦即如何构造n阶幻方。

奇数阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：【例1.1.1】（拉丁方）36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。

问能否把这些军官排成6×6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。

A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6B2 C3 D4 E5 F6 A1B3 C4 D5 E6 F1 A2C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3F6 A1 B2 C3 D4 E5 F6【例1.1.2】（计数——图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。

求本质上不同的染色方案。

举例：形式总数：43＝81种。

实际总数（见第6章）：L ＝()32334124⨯++＝24 【例1.1.3】（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。

习题四（容斥原理）1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则22001002A ⎢⎥==⎢⎥⎣⎦，3200663A ⎢⎥==⎢⎥⎣⎦，5200405A ⎢⎥==⎢⎥⎣⎦，7200287A ⎢⎥==⎢⎥⎣⎦， 112001811A ⎢⎥==⎢⎥⎣⎦，132001513A ⎢⎥==⎢⎥⎣⎦，232003323A A ⎢⎥==⎢⎥⨯⎣⎦， 252002025A A ⎢⎥==⎢⎥⨯⎣⎦，272001427A A ⎢⎥==⎢⎥⨯⎣⎦，2112009211A A ⎢⎥==⎢⎥⨯⎣⎦， 2132007213A A ⎢⎥==⎢⎥⨯⎣⎦，352001335A A ⎢⎥==⎢⎥⨯⎣⎦，37200937A A ⎢⎥==⎢⎥⨯⎣⎦， 3112006311A A ⎢⎥==⎢⎥⨯⎣⎦，3132005313A A ⎢⎥==⎢⎥⨯⎣⎦，57200557A A ⎢⎥==⎢⎥⨯⎣⎦， 5112003511A A ⎢⎥==⎢⎥⨯⎣⎦，5132003513A A ⎢⎥==⎢⎥⨯⎣⎦，7112002711A A ⎢⎥==⎢⎥⨯⎣⎦， 7132002713A A ⎢⎥==⎢⎥⨯⎣⎦，111320011113A A ⎢⎥==⎢⎥⨯⎣⎦，2352006235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 2372004237A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231120032311A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，231320022313A A A ⎢⎥==⎢⎥⨯⨯⎣⎦ 2572002257A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251120012511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，251320012513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 271120012711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，271320012713A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， 21113200021113A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，3572001357A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，351120013511A A A ⎢⎥==⎢⎥⨯⨯⎣⎦351320013513A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，371120003711A A A ⎢⎥==⎢⎥⨯⨯⎣⎦，…， 235720002357A A A A ⎢⎥==⎢⎥⨯⨯⨯⎣⎦，…，23571113200023571113A A A A A A ⎢⎥==⎢⎥⨯⨯⨯⨯⨯⎣⎦， 所以 23571113200(1006640281815)(3320149713965533221)(6432211110111i i j i j k i j k lii ji j ki j k li j k l m i j k l m ni j k l mi j k l m nA A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+-+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑∑0)00041+-+=但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中， 故所求的素数个数为：416146+-=2．问由1到2000的整数中：（1）至少能被2，3，5之一整除的数有多少个？ （2）至少能被2，3，5中2个数同时整除的数有多少个？ （3）能且只能被2，3，5中1个数整除的数有多少个？ 解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，则2200010002A ⎢⎥==⎢⎥⎣⎦，320006663A ⎢⎥==⎢⎥⎣⎦，520004005A ⎢⎥==⎢⎥⎣⎦， 23200033323A A ⎢⎥==⎢⎥⨯⎣⎦，25200020025A A ⎢⎥==⎢⎥⨯⎣⎦，35200013335A A ⎢⎥==⎢⎥⨯⎣⎦， 235200066235A A A ⎢⎥==⎢⎥⨯⨯⎣⎦， （1）即求235A A A ++，根据容斥原理有：235235232535235()1000666400(333200133)661466A A A A A A A A A A A A A A A ++=++-+++=++-+++=（2）即求232535A A A A A A ++，根据容斥原理有：232535232535235235235235()333200133266534A A A A A A A A A A A A A A A A A A A A A A A A ++=++-+++=++-⨯=（3）即求[1]N ，根据Jordan 公式有：1112233235232535235[1]2()310006664002(333200133)366932N q C q C q A A A A A A A A A A A A =-+=++-⨯+++⨯=++-⨯+++⨯=3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。

第二章母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法新方法：母函数方法。

基本思想：把离散的数列同多项式或幂级数一一对应起来，算。

2.1 母函数（一）母函数（1）定义【定义2.1.1】对于数列{}n a ，称无穷级数()∑∞=≡0n n n x a x G 为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例【例2.1.1】有限数列rn C （r ＝0, 1, 2, …, n ）的普母函数：()x G ＝nn n n n nx C x C x C C ++++ 2210＝()nx +1【例2.1.2】无限数列{1, 1. …, 1, …}的普母函数：()x G ＝ +++++nx x x 21＝x-11（3）说明● n a 可以为有限个或无限个。

● 数列{}n a 与母函数一一对应。

{0, 1, 1, …, 1, …}↔ +++++n x x x 20＝xx -1 ● 将母函数视为形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”。

（4）常用母函数（二） 组合问题 （1）组合的母函数【定理2.1.1】组合的母函数：设{}m m e n e n e n S ⋅⋅⋅=,,,2211 ,且n 1＋n 2＋…＋n m ＝n ，则S 的r 可重组合的母函数为()x G ＝∏∑==⎪⎪⎭⎫ ⎝⎛mi n j j i x 10＝∑=n r r r x a 0其中，r 可重组合数为rx 之系数r a ，r ＝0, 1, 2, …, n 。

理论依据：多项式的任何一项与组合结果一一对应。

【例2.1.3】设有6个红球，7个黑球，8个白球，问 （1） 共有多少种不同的选取方法，试加以枚举？ （2） 若每次从中任取3个，有多少种不同的取法？ （解）（1）元素符号化（x ，y ，z ↔红、黑、白球），元素的个数以符号的指数区分。

母函数G (x , y , z ) ＝(1＋x ＋x 2) (1＋y ) (1＋z )＝1＋(x ＋y ＋z )＋(x 2＋xy ＋xz ＋yz )＋(x 2x ＋x 2x ＋xxx )＋( x 2yz )5种情况：① 数字1表示一个球也不取的情况，共有1种方案； ② 取1个球的方案有3种，即红、黑、白三种球只取1个； ③ 取2个球的方案有4种，即2红、1红1黑、1红1白、1黑1白； ④ 取3个球的方案有3种，即2红1黑、2红1白、三色球各一； ⑤ 取4个球的方案有1种，即全取。