1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5；
解：（1）：由|a-b|=5?a-b=5或者a-b=-5，
由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|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题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？
解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y
在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2
所以总的排列数为上述6种情况之和。
1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若
(a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。
解：(a) 可以考虑插空的方法。
n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。
则男生不相邻的排列个数为
p
p n m
n
n
1+?
(b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。
(c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！
(这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！
1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。
解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！
n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)!
所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１
1.7题 试证：)2()2)(1(n n n ++被2n
除尽。
证明：因!)!12(!2)!2(-=n n n n
!)!12(2
!)!
2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n
n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。
1．8题 求4010和30
20的公因数数目。
解：因为1030404040405*5*25*210== 30
20403060305*2*25*220==
它们最大公因子为30
405*2转化为求 最大公因子 能除尽的整数个数，能除尽它的整数是
300,400,5*2<=<=<=<=b a b
a
根据乘法法则，能除尽它的数个数为 41*31=1271
1.9题 试证2
n 的正除数的数目是奇数。
证明：设有20,a n n b n <<<<, 则一定有表达式2
n a b =?，
则 可知符合范围的a 和b 必成对出现，所以为偶数。
又当a=b=n 时，表达式2n =a ?b 仍然成立。 所以2n 的正除数的数目是“偶数1+”为奇数。 1.10题 证任一正整数n 可唯一地表成如下形式:
,0≤a i ≤i,i ＝1,2,…。
证：对n 用归纳法。
先证可表示性：当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。 对于n,设k!≤n ＜(k+1)!,即0≤n -k!＜k·k!
由假设对n-k!,命题成立，设
，其中a k ≤k -1,，命题成立。
再证表示的唯一性：设
, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }
a j ·j!+a j-1·(j-1)!+…+a 1·1! =
b j ·j!+b j-1·(j-1)!+…+b 1·1!,
∑∑∑∑?-≥?-≥?>≥?-=?-!)(!!!!)(!)(i a b i a b i i j i a b j b a i i i i i i j j 矛盾，命题成立。
1.11题 证明nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.
证：(1)!(1)!(1)!
(1,)(1)(,1)!(1)!(1)!(1)!(1)!(1)!
n r n r n nC n r n
r C n r r n r r r n r r n r -+?+?-====++?--+??--+?--
所以左边等于右边
组合意义：等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个；
等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。 所以两种方案数相同。 1.12题 证明等式：
1
1
2
),(-==∑n n
k n k n kC
证明： []11
110111(1,0)(1,1)(1,1)211n
n n n k k s n n n n n n n C n C n C n n n k k s --===---??????====-+-++--== ? ? ?--??????
∑∑∑L 等式左边右边 1.13题 有N 个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。
解题思路：（取法由大到小）
第1步：从N 个数由大到小取一个数做为第一组，其它N-1个数为第二组，
组合数为：c （n,1）*{c(n-1,1)+c(n-1,2)-…+c(n -1,n-1)}
第2步：从N 个数由大到小取两个数做为第一组，其它N-2个数为第二组，
组合数为：c （n,2）*{c(n-2,1)+c(n-2,2)-…+c(n -2,n-2)} …
第n-2步：从N 个数由大到小取n-2个数做为第一组，其它2个数为第二组，组合数为：c （n,n-2）*{c(2,1)} 第n-1步：从N 个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：c （n,n-1）*{c(1,1} 总的组合数为：
(,1){(1,1)(1,2)(1,1)}(,2){(2,1)(2,2)(2,2)}
(,2){(2,1)(,1)(1,1)}
C n C n C n C n n C n C n C n C n n C n n C C n n C ?-+-++--+?-+-++--+
+-?+-?
1.14 题 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？
解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，
第2步从特定引擎一边的2个中取1个有C(2,1)种取法，
第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)?C(2,1)?C(2,1)=12种方案。
1.15题 求1至1000000中0出现的次数。
解：当第一位为0时，后面6位组成的数可以从1-100000，共100000个0；
当第二位为0时，当第一位取0-9时，后面5位可以取1-9999，此外当第一位取0时，后面5位还可以取为
10000，这样共有9999*10+1=99991个0；
同理第三位为0时，共有99901个0； 第四位为0时，共有99001个0；第五位为0时，共有90001个0；
第六位为0时，只有1个0；
这样总共的0数为：100000+99991+99901+99001+90001+1=488895。
1.16题 n 个相同的球放到r 个不同的盒子里，且每个盒子里不空的放法。
解：如果用“O”表示球，用“|”表示分界线，就相当于用r-1个“|”把n 个“O”分成r 份，要求是每份至少有一个球。如下图所示： 00|00000000|00000000|00000|000000……
对于第一个分界线，它有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)。 1.18题 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？
解：要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有!55
5=p 。所以共有8*5！种排列。 8种排列如下两类。因为要求空盒不相邻，途中1代表球
a) 1 1 1 1
b) 1 1 1 1
在a)中 剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种 1.17题 n 和r 都是正整数，而且n r ≤，试证下列等式： 1111
11
11
1
1
1
()()
(1)()
,()
()
!()
n
n n n n n r r r
r r
r
n n n n n n r
r
r
r r
r r r n a n b n r c r n
n r
d r
e r r p p
p p p
p
p
p p
p
p
p
p
----++-----==-+=
<-=
+=++
++
L
解：(a) p
p
n r
n r r n n r n n n n
=
-=--?
=--)!(!
)!()!1(11
等式成立。
(b) p p n r n
r r n n r n n r n r n =-=+-?
+-=+--)!
(!
)!1(!)1()
1(1等式成立。
(c) p p n r n r r n n r n n r n n r n n =-=---?-=--)!
(!
)!1()!1(1等式成立。 (d)
11
!!!(1)!(1)!!!(1)!
()!(1)!(1)!(1)!(1)!(1)!
n n n r
r r
n n n n r n n n r r n n r r r n r n r n r n r n r n r p
p
p
+--++-?+?++=
+?=+?===--+-+-+-++-
(e)利用(d)的结论可证明本题。
111
1
1
1
1
1
1211
1
1
1
1
112111
1
1
1
!()n n r
r n n r
r r r r
r r r r r
r r n n
r
r r r r r r r r n n n r
r r r r r
r r r r r r r r r r r r r r p
p
p
p p p p
p p p p p p p p p p p p
--------++------+++-+----++
++
=
++++=++++++=+++++=L L L L
1.19题 n+m 位由m 个0，n 个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。 解：m 个0进行排列，留出m+1个空挡，任选n 个空挡放1，共有C(m+1,n)种方案.
1.21题 一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。
解：C （6,2）*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/14
1.20 题 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？
解：1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志 C(10,4)*C(15,1)*C(10,2)=141750 2. .甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。 C(10,3)*C(15,2)*C(4.1)*C(10,1)=504000
3. .甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志. C(10,2)*C(15,3)*C(4,2)=122850 1+2+3即为所求，总的方案数为768600 1.22题 求图1-22中从O 到P 的路经数: (a) 路径必须经过A 点; (b) 路径必须过道路AB; (c) 路径必须过A 和C (d) 道路AB 封锁(但A,B 两点开放) 解: (a)分两步走O(0,0)→A(3,2) A(3,2)→P(8,5)，根据乘法法则: 560353223=???
?
??+????? ??+=N
(b)分两步走O(0,0)→A(3,2), B(4,2)→P(8,5)，根据乘法法则:350334223=?
??
? ??+????? ??+=N
(c)分三步走: O(0,0)→A(3,2), A(3,2)→C(6,3), C(6,3)→P(8,5), 根据乘法法则: 240
222113223=????
??+????? ??+????? ??+=N （d ）AB 封锁路径数加必经AB 路径数即O(0,0)→P(8,5)的所有路径数有加法法则可得：
9373501287334223585=-=???
?
??+????? ??+-???? ??+=N
1.23题 令s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z ∈s, x 111||223n k n n T k =++????= =+ ? ????? ∑ 证明：要确定x,y,z 的取值，有两种方法， (1)可先确定z,由题意可得 当z=2时，x 可取1，y 可取1，根据乘法法则，x,y 取值共有1×1=12种可能； 当z=3时，x 可取1,2，y 可取1,2，根据乘法法则，x,y 取值共有2×2=22种可能； 当z=4时，x 可取1,2,3，y 可取1,2,3,根据乘法法则，x,y 取值共有3×3=32种可能； …… 当z=n+1时，x 可取1,2,…,n,y 可取1,2,…,n,根据乘法法则，x,y 取值共有n×n=n 2种可能。 根据加法法则，当z 取2,3,…,n+1时，x,y 取值共有2 2 2 2 1 12n k n k =+++= ∑…种可能。故2 1 ||n k T k == ∑。 (2)由x ①x=y ??? ； ②x ???； ③y ??? 。 所以满足题意的x,y,z 的组合数为12n +?? ???+13n +?? ?? ?+13n +?? ???＝11223n n ++????+ ? ?????。 由于这两种方法是等价的，故可得2111||223n k n n T k =++???? ==+ ? ????? ∑。证毕。 1.24题 A={(a , b)|a , b ∈Z, 0≤a ≤9,0≤b ≤5} (a) 求x-y 平面上以A 作顶点的长方形的数目. (b) 求x-y 平面上以A 作顶点的正方形数目. 解(a)：如图(a)，从图中可以看出，对于x-y 平面上满足题意的任一顶点A(a,b),除它本身以外，横坐标取值有9种可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为9×5=45个。 解(b)：如下图(b)，网格左边是b 的取值，下面是a 的取值。网格里是x-y 平面上对应每个顶点A(a,b)所得的正方形的数目。 1.26题 S={1,2,……，1000}，a,b ∈S,使ab≡0 mod 5,求数偶{a,b}的数目 解：根据题意，ab 可以整除5，2*C （200，1）*1000=400000 1.25题 平面上有15个点P 1,P 2。。。Ｐ15，其中P 1P 2P 3P 4P 5共线，此外不存在3点共线的。 (1)求至少过15个点中两点的直线的数目 (2)求由15个点中3点组成的三角形的数目 解：1)由题意知：P 1P 2P 3P 4P 5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：C 102=45 又因为P 1P 2P 3P 4P 5共线，所以可算作一条至少2点相连的直线 所以至少过15个点中两点的直线的数目=50+45+1=96 2)有三种情况 a ：没有P 1P 2P 3P 4P 5这五个点的三角个数：C 103=120 b ：有这五个点的其中一个点：5*C 102 225 c ：有着五个点的两个点：10*C 52=100 由15个点中3点组成的三角形的数目=425 故数目为C(15,2)-C(5,2)+1 (b) C(5,0)C(10,3)+C(5,1)C(10,2)+C(5,2)C(10,1) 1.27 题 6位男宾，5位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾在一起有多少种方案？（3）一女宾A 和两位男宾相邻又有多少种方案？ 解 ：（1）若5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入 Q （6，6）*6*5*4*3*2=86400 （2）把5位女宾看成一个整体，然后插入 Q （6，6）P(6,5)=86400 （3）P （6，2）*Q （9，9）=194000 1.28题 k 和n 都是正整数，kn 位来宾围着k 张圆桌而坐，试求其方案数。 解：若每个圆桌的的人数相等，则每个桌子有n 个人。因为圆周排列的个数为 r p n r 因此本题的结果为 k n kn n n n kn )! ()!(=? 。 1.29 题 从n 个对象中取个r 做圆排列，求其方案数目。1<=r<=n 解：c(n,r)*Q （r,r ） =c(n,r)*(r-1)! 1.31题 试证任意r 个相邻数的连乘：(1)(2)()n n n r +++ 被r ！除尽. 证明：由 P （n ,r ）=n*(n-1)…（n-r+1） 可知：（n+1）（n+2）…（n+r ）= p （n+r,r ）=c （n+r,r ）* r! 所以 [（n+1）（n+2）…（n+r ）]/r!= p （n+r,r ）/ r! = c （n+r,r ） 故任意个相邻数连乘可被r ！除尽。 1．30题 （1）???? ??r n =n/r ???? ??--11r n ， 1≤r ≤n ；（2）???? ??r n =（n-r+1）/r ???? ??-1r n , 1≤r ≤n ；(3) ? ?? ? ??r n =n/(n-r)???? ??-r n 1 , 0≤r ≤n ； 解：（1）：=??? ? ??r n n!/(r!(n-r)!) n/r ???? ??--11r n =n/r*((n-1)!/((r-1)!(n-r)!))= n!/(r!(n-r)!)=上式 所以两式相等 （2）：=???? ??r n n!/(r!(n-r)!) (n-r+1)/r ??? ? ??-1r n =（n-r+1）/r*((n!)/((r-1)!(n-r+1)!))= n!/(r!(n-r)!)=上式 所以两式相等 （3）：=??? ? ??r n n!/(r!(n-r)!) n/（n-r ）???? ??-r n 1=（n-1）!/(r!(n-r-1)!))= n!/(r!(n-r)!)=上式 所以两式相等 1.32题 在a, b, c, d, e, f, x, x, x, y, y 的排列中，要求y 必须夹在两个x 之间，问这样的排列数等于多少？ 解：满足y 必须加在两个x 之间应为 x y x y x 然后再把a ，b ，c ，d ，e ，f 插入，a 插入时有6种选择， b 插入时有7种选择，c 插入时有8种选择，d 插入时有9种选择，e 插入时有10种选择，f 插入时有11种选择， 由此可得排列数 N=11*10*9*8*7*6=11!/5! 1.33题 已知r ，n ，k 都是正整数，nk r ≥，将r 个无区别的球放在n 个有标志的盒子里，每盒至少k 个球，试问有多少种方案？ 解：首先从r 个球中取出nk 个球放入n 个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球 放的时候都有n 中可能。因此方案数为nk ) -(r n . 1.34 题 在r,s,t,u,v,w,x,y,z 的排列中求y 居于x 和z 中间的排列数 解 ： 2*（5+4+3+2+1）*6！=2430 1.35题 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点？ 解：根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个； 与它不相邻的顶点有6条对角线（有1条与它重复的），这样的点8个； 因此 （2* C （7，1）* C （7，1）+8* C （6，1）* C （7，1））*（9+1） =4340 1.36题 试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数 证明：设N=P 1a1 P 2a2。。。P n an ，P 1，P 2，。。。P n 是n 个不同的素数，每个能整除尽数n 的正整数都可以选取每个素数P i 从0到a i 次，即每个素数都有a i +1种选择，所以能整除n 的正整数的数目为(a 1+1)(a 2+1)。。。(a i +1)个。而设M=N 2=P 12a1 P 22a2。。。P n 2an ，能被(2a 1+1)(2a 2+1)。。。2(a i +1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。 1.37题 .给出???? ?????? ??0r m n +???? ??+???? ??--1111r m n +???? ??+???? ??--2222r m n +…+???? ??+???? ??-m m r m n 0=??? ? ??++m r n 1的组合意义。 解： ） P 点到P’点只有一步；???? ??--+-k m k m m n =???? ??--k m k n 表示P’点到B 点的路径数;? ?? ? ??++m r n 1表示（0，0）点到B 点的路径数。 所以0点到B 点的路径由0点到P 点再从P 点到P’点，最后从P’点到达B 点。 ∑ M ???? ??+k k r *1*???? ??--k m k n =∑M 0???? ?????? ??0r m n +???? ??+???? ??--1111r m n +???? ??+???? ??--2222r m n +…+???? ??+???? ??-m m r m n 0=??? ? ??++m r n 1 1.41 题 分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。 解：利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号，生成已知排列序号算法： 设 int M 为每一排列的对应序号初始时：P 1_P 2_...P i-1_P i _P i+1_...P n _ (其中P 1_ 满足关系式P i-1 使P i-1与 P j 互换得(p _) = P 1_P 2_...P i-1_P i _P i+1_...P n _ IV. (p _) = P 1_P 2_...P i-1_P i _P i+1_...P n _ 中的P i _P i+1_...P n _部分的顺序逆转，得下一排列。 V. 判断(p _)排列是否与给定排列相同 ，相同则输出M ， ELSE M=M+1 GOTO Ι （2）给定序列号计算排列算法： 设 Int M 为每一排列的对应序号，M=N （N 为给定序号） 设 Int K 为循环次数 FOR （K=1；K++；K <=N ） { 满足关系式P j-1 (p _) = P 1_P 2_...P i-1_P i _P i+1_...P n _ 中的P i _P i+1_...P n _部分的顺序逆转，得下一排列 } 输出(p _)排列。 1.38题 给出? ?? ? ??++=???? ??++???? ??++???? ??++???? ??1121r n r n r r r r r r 的组合意义。 解：设A={1a ,2a ,….,1+-r n a ,……,1+n a },从A 中取r+1个元素组合成C ，考虑以下n-r+1种情况： (1) 1a ∈C ，则A 需要从A\{1a }中取r 个配合，构成C ，共??? ? ??r n 种可能 (2)c a ?1，,2c a ∈则需要从},{\21a a A 中取r-1个，加上2a 构成C ，共??? ? ??-r n 1中可能 …… (n-r)，，C a C a a a r n r n ∈?---121,...,,则需从A\{r n a a a -,...,,21}中取r 个组合，再加上r n a -构成C ，共??? ? ??+r r 1种可能。 ,,...,,)1(21C a a a r n r n ?+--这时只有? ?? ? ??r r =1种可能。 故???? ??r n +???? ? ?-r n 1+???? ??-r n 2+…+???? ??+r r 1+???? ??r r =???? ??++11r n （法二）C(n+1,r+1)是指从n+1个元素a 1, a 2,…,a n+1中任取r+1个进行组合的方案数。 左边：若一定要选a n+1,则方案数为C(n,r).若不选a n+1,一定要选a n , 则方案数为C(n-1,r). 若不选a n+1,a n ,…a r+2, 则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。 1.39 题 证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m -n,0)=2n C(m,n) 证明：由公式C(n,l)C(l,r)=C(n,r)C(n-r,l-r) 其中：l>=r 得： C(m,0)C(m,n)=C(m,n)C(n,0) 同理： C(m,1)C(m-1,n-1)=C(m,n)C(n,1) … C(m ,n)C(m-n,0)=C(m,n)C(n,n) 由上知：左边=[C(n,0)+C(n,1)+ … +C(n,n)]C(m,n) 由()n x y +=C(n,0)n x +C(n,1)1n x y -+C(n,2)22n x y -+…+C(n,n)n y 令x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)=2n 左边=2n C(m,n)=右边 命题得证。 1.40题 从n 个人中选r 个围成一圆圈，问有多少种不同的方案？ 解：圆排列:共有P(n,r)/r 种不同的方案。 1.48题 在由n 个0及n 个1构成的字符串中，在任意前k 个字符中，0的个数不少于1的个数的字符串有多少？ 解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。 1.42题 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法. (b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. 解：1：给定排列求相应序号： 设 Int I 为每一排列的对应序号 I=1 （初始化） 假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列 123 S [1]1 2 [][][] 1 q 0 A[1n]B[1n] I I I 1 k n 2 A i n A i i D i i E i S S ←←←←-←←+：从到作 始，，终；：； 判断：是否与：相等若相等则输出值否则；：从降到作 始 D[k]D[k]E[k]; p D[k]; p k E[k]-1; p 0 E[k]1, q q 1 ←+←=←=←←+若则作否则作 始若则作 始终2 p p q; r A[p]; A[p]A[p 1]; A[p 1]r; S ←+←←++←否则作始转终终终 2：给定序号求相应排列： 设 Int I 为每一排列的对应序号 I=1 （初始化） M 为给定序列号 M=N 假定A[1：n]和E[2：n]；D[2：n]；都是整数数组 123 S [1]1 2 [][][] 1 q 0 I i 1n A[i] I I 1 k A i n A i i D i i E i S M S ←←←←-←←+：从到作 始，，终；：； 判断是否与相等 若相等则从到输出；否则；：从n 2 D[k]D[k]E[k]; p D[k]; p k E[k]-1; p 0 E[k]1, q q 1 ←+←=←=←←+降到作 始若则作否则作 始若则作 始终2 p p q; r A[p]; A[p]A[p 1]; A[p 1]r; S ←+←←++←否则作始转终终终 (a) 由给定排列生成其下一个排列的算法 。 转指向；大的数一律改变箭头的比：数互换位置。 和它箭头所指一侧相邻，设为的数值最大者，求处于活动状态各数中：停止。中无一处于活动状态则若在：生成下一个排列 从排列13221121S m m m S p p S p p S p p p p n n == 1.43题 对于给定的正整数N ，证明，当11222 N N N N K N -+??=???或若是奇数若是偶数时，C(N,K)是最大值。 证明：要证明C （N ，K ）是最大值，只需证明C （N ，K ）大于C （N ，K-1）即可 根据以往证明大小值的经验，可以用相减或是相除的方法来证明，就此题，相减不合适，采用相除可以消除等式中的一些项 C （N ，K ）/ C （N ，K-1）=（N ！/K ！（N-K ）！）*（（K-1）！（N-K+1）！/N ！） =（N-K+1）/K 当n 为偶数，k=n/2时 （N-K+1）/K=（（n+2）/n ）*（2/n ）=（n+2）/n >1 当n 为奇数,k=(n-1)/2时 （N-K+1）/K=((n+3)/2) * (2/(n-1))=1+4/(n-1) >1 当n 为奇数, k=(n+1)/2时 （N-K+1）/K=((n+1)2) * (2/(n+1)) =1 综上所述,当n 取以上三种情况, C （N ，K ）取最大值 1.46题 证明在由字母表{0,1,2}生成的长度为n 的字符串中. (a) 0出现偶数次的字符串有31 2 n +个； (b) 13122...2022n n n n q n n n q --?????? ++++= ? ? ??????? ，其中22n q ??=??. 证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。 假设当n=k 时,0出现偶数次的字符串有(3k +1)/2种。总的字符串有3种。0出现奇数次的字符串有(3k -1)/2种。 当n=k+1时，0出现偶数次的字符串包括两部分： n=k 时,0出现偶数次再增加一位不是0的，共有2(3k +1)/2种，0出现奇数次再增加一位0,共有(3k -1)/2种。 所以共有2(3k +1)/2+(3k -1)/2=(3k+1+1)/2种，证毕。 (b) 等式左边第m 项是0出现m 次的字符串数，总和就是0出现偶数次的字符串数， 右边由(a)得是0出现偶数次的字符串数，两边显然相等。 1.44题 （a ）用组合方法证明n n 2)!2(和n n n 32)! 3(?都是整数。 （b ）证明) !(12 )!(n n n +是整数。 解：(a) ①方法一：因为：!)!12(!2)!2(-??=n n n n 所以!)!12(!2! )!12(!22)!2(-?=-??= n n n n n n n n !)!12(!-?n n 是整数，因此 n n 2 )! 2(是整数。 方法二：设有2n 个不同球放入n 个不同的盒子里，每盒两个，这个方案数应该是整数。 对2n 个球进行排列得到方案数为(2n)!。 而把2个球放入同一个盒子里不计顺序， 应该把全排列数除掉这些重复计算的次数，n 个盒子内部的排列共重复计算了2 次。 得到2n 个不同球放入n 个不同的盒子里，每盒两个的方案数 n n 2 )! 2( ②若有3n 个不同的球,放入n 个不同盒子,每个盒子放三个，这个方案应该是整数。 对这3n 个球进行排列得到方案数为(3n)!。 而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数， n 个盒子内部的排列共重复计算了3！次。 得到3n 个不同的球放入n 个不同的盒子里，每盒三个的方案数 n n n n n 23)! 3()!3()!3(?= (b) 有2 n 个不同的球，放入n 个相同的盒子里，每盒n 个，求方案数，方案数应该是一个整数。 按前面(a)的方法，应该得到(n 2)!/(n!)n 是整数。另外由于n 个盒子相同，放入不同的盒子是没有区别的， 应该把n 个盒子的排列数n!除去。 因此得到(n 2)!/(n!)n+1是整数。 1.49 题 在1到n 的自然数中选取不同且互不相邻的k 个数,有多少种选取方案？ 解: 设从1-n 中选取互不相邻的k 个数的方案为g(n,k)。若选n ，则方案为g(n-2,k-1),若不选n,则方案数位g(n-1,k). 显然g(n,k)=g(n-2,k-1)+g(n-1,k)，且只有当n≥2k -1时,g(n,k)>0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2,k)=0. 1.45题 (a) 在2n 个球中，有n 个相同. 求从这2n 个球中选取n 个的方案数. (b) 在3n+1个球中，有n 个相同. 求从这3n+1个球中选取n 个的方案数. 解(a ）：有n 个相同就有n 个不相同 取n 个不相同和0个相同的为C(n,n), 取n-1个不相同的球和1个相同的球为C(n,n-1)，等等。 所以总的方案数为 ()()()n n n C n C n C 2,1,0,=+++ 解(b ）：方法同上，方案数为()()()n n C n C n C ,121,120,12++++++ 由于C(2n+1,0)=C(2n+1,2n+1),… ,C(2n+1,n)=C(2n+1,n+1) ()()() 12212,121,120,12+=+++++++n n n C n C n C 则()()()21212 21,021,121,22n n C n C n C n n +++++ ++== 1.47题 5台教学机器m 个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？ 解：当使用第1台机器的学生为n 个时，使用第2台机器的学生也为n,从m 个学生中选出2n 个使用这两台机器， 剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。 所以总的方案数为 ?? ????=∑=-23 ),2()2,(0 ) 2(m q n n C n m C q n n m 1.50题 (1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？ (2)在有m 个0，n 个1组成的字符串中，出现01或10的总次数为k 的字符串，有多少个？ 解：(1)、先将5个00000排成一排，1若插在两个0中间，即：“010”则出现2个“01”或“10”； 若插在两端，则出现1个“01”或“10”；要使出现“01”，“10”总次数为4，有两种办法： 1、把两个1插入0的空当内，剩下的1插入1的后面（类似010111000）。 2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。（类似10100011）。 由1和2得：30*3*31 424=+C C (2)、m 个0产生m-1个空当。 若k 为偶数时：要得到出现“01”与“10”总次数为k ，可以先按上题中1的情况讨论，则在m-1个空当中分别插入2 k 个1即可，也就是2 1k m C -。剩下的 1如何插入的问题与书P20页的定理1.2类似(在n 个不同元素中取r 个允许重复的组 合，其组合数为（C （n+r-1,r)），在这里无区别的球的个数也就是剩下的1的个数（即n-2 k ），盒子的个数也就是插入 到m-1个空当中的1的个数(即2 k )，则得出剩下的1的插入方法有21k n n C - -。即第一种情况的总的插入方法为：2121 *k n n k m C C - --。 同理可得，按2的情况讨论后的第二种情况的总的插入方法为：222 122 1 *--- ---k n n k m C C 。 1和2得总的插入方法为：222 1221 2121 **--- ---- --+k n n k m k n n k m C C C C 。 若k 为奇数时：则必有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使k 为奇数。 所以插入的总方法为：2 1121 1 **2+- ---k n n k m C C 。 1.51 题 从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？ 解：相当于从N={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种 1.52题 从s={1,2,n}中连取k 个数，使之没有两个数相邻，求不同方案数。 解：在n 个数中选k 个数，使之没有两个数相邻，相当于在n-k+1位置中插入k 个数，k 个数中没有俩个数相邻。 有! )! 1(1k k n C k k n +-= +-种方案。有定理1.4直接可得。 1.53题 把n 个无区别的球放进有标志1，2，…，n 的n 个盒子中，每个盒子可放多于一个球，求有多少种方案？ 解：把n 个无标志的球放进n 个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是 ???? ??-+n n n 1=??? ? ??-n n 12 1.54题 .m 个1，n 个0进行排列，求1不相邻的排列数.设n>m. 解：相当于n 个0排列后,使m 个1做不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况， 第二个是n 种情况…第m 个1插入就有n-m+1种情况。 所以是（n+1）（n ）（n-1）…（n-m+1），即此题解为p n+1 m 。 1.55题 偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。 证明： 根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差， 如果所得的差能被11整除，那么这个整数必能被11整除。 例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2 因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除， 所以原题成立。证毕。 1.56 题 n 个男人与n 个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又m 个女人n 个男人，且m 解：根据题意，两个女人之间坐1个男人的方案数Q (n,n)* P(n,n) 无两个女人并坐的方案数Q (n,n)* P (n,m) 1.57 题 n 个人分别沿着两张圆坐下，一张r 人，另一张个n-r 人，试问有多少种不同的方案数？ 解： C （n,r ）*(r-1)!(n-r-1)! 1.58题 一圆周上n 个点标以n ,,2,1 。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？ 解：这些直线交于圆内有C （n,4）个点 每4个点形成矩形，其对角线有一个交点，故圆内交点有： ) 3)(2)(1(241 1234)3)(2)(1()4,(---=???---= n n n n n n n n n C 因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点， 求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n 个点取出四个进行组合 2.1题 求序列{ 0，1，8，27， 3 n }的母函数。 解：由序列可得到3 2 3 3 3()23n G x x x x n x =+++++ 因为 231 11n x x x x x =++++++- 2311()'12341n x x x nx x -=++++++- 设 2311 ()()'23(1)1n n p x x x x x n x nx x -==++++-+- 2 2 222 21 [()] '123(1)n n p x x x x n x n x -- =+++ + +-+ 设 2 2 2 3 212()[()]'23(1)n n q x x p x x x x n x n x -==+++ +-+ 33 23231 [()] '123(1)n n q x x x n x n x -- =++++-+ 3233 313[()]'23(1)n n x q x x x x n x n x -=+++-+ 由以上推理可知[()]'x q x = ,[7*94*(6)], n n +- 所以可通过求得[()]'x q x 得到序列的母函数：32 ()4G x x x x =++ 2321 ()()[34(3)]6 n H x F x dx x x n x +==++ ++? 2.2题 已知序列343,, ,,333n ?+????????? ? ? ???????? ?，求母函数 解： 3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1n n n n G x x +++= +++ =1[3.2.1 4.3.2(3)(2)(1)]6 n x n n n x ++++++ 21 1()()[3.2 4.3(3)(2)]6n F x G x dx x x n n x +==+++++? 232 1()()[34(3)] 6n H x F x d x x x n x +==++++? 3431 ()()[]6 n I x H x dx x X x ++==++? 因为23 111n x x x x +=+++ ++ - 所以2 11()(1)61I x x x x =---- 所以31()[ ]'''61x G x x =-就是所求序列母函数 2.3题 已知母函数2 378()1354x G x x x += --，求序列{n a }。 解：2378()1354x G x x x +=--=x x x B x A 614 9176191+- -=++- 由23111n x x x x +=+++++-得 277(19(9)(9)) 19n x x x x =++++- 24 4(1(6)(6)(6))16n x x x x =+-+-++-+ 所以由两式相加得：对应序列{n a }={11，39， ,[7*94*(6)], n n +-} 2.4题 已知母函数2 39()156x G x x x -= --，求序列{n a }。 解：2 39()156x G x x x -=--=12 18171817A B x x x x +=+-+-+ 则n a =82*(1)*7n n +- 2.5题 设2n n G F =，其中n F 是Fibonacci 数。证明：1230n n n G G G ---+=，n=2. 3.4…..求{012,,, G G G }的母函数。 解：(1).已知2n n G F = 则123n n n G G G ---+=222243n n n F F F ---+ 22122n n n F F F --=+ 21222n n n F F F ---=+ 22232n n n F F F ---=+ 则222243n n n F F F --=- 则1230n n n G G G ---+= (2)．011 22 ()()n n n n G x G G x G G x ∞ --==++ +∑ =1 2 20112 2 2 n n n n n n G G x x G x x G x ∞ ∞ ----==+++∑∑ =2 2 0102 2 ()n n n n n n G G x x G x G x G x ∞ ∞ --==++-+∑∑ =2010()()G G x xG x xG x G x ++-+ =2 1()()xG x x G x x ++- 2 1()1x G x x x -=-- 2.6题 求序列{1，0，2，0，3，0， }的母函数。 解：序列n a = 20 (1)n n n x ∞ =+∑=2200n n n n nx x ∞ ∞ ==+∑∑=2200 11(21)22n n n n n x x ∞∞==++∑∑=22 111()'2121x x x +--=221(1)x - 2.7题 设 +++++++=n x n x x x G 2642)1(4321=1/(1-x^2)^2 求G x G x 222)1(,)1(-- 解：设246 211234(1)111n x T G x x x n x x x ==+++++++= -= --? L L 2 2)1(1)1(11x x x x x x G -=-+-=?? ? ??-=ι 所以 1） +++++=-=--=-n x x x x x x G x 2422 2222 111)1()1()1( 2）1)1(1)1()1(222222=--=-x x G x 2.8题 求下列序列的母函数：(1)1,0,1,0,1,0，… (2)0,-1,0,-1,0,-1,… (3)1,-1,1,-1,1,-1,… 解：(1) +++++=n x x x G 24212 11 x -= (2) ------=+1 253n x x x x G 242221(1)11 n x x x x x x x x =-+++++=-= --L L (3) +-+-+-++-n n x x x x x )1(14 3 2 2 2424 22 111(1)(1)111x x x x x x x x x x x --=+++-+++=-=---L L 2.9题 设 +??? ? ??++++++=n x n x x x G 22106313 2 证明：(1) +++++++=-n x n x x x G x )1(4321)1(32 (2) +++++=-n x x x G x 221)1( (3)因为1)1(3 =-G x ，所以有3 )1(1 x G -= 证明（1）2232 211 136(1)123(1)2(1)(1) n n n G x x x x G x x n x x x +??=+++ ++= ∴-==++++++ ?--?? （2）展开(1-x 2)G= (1+x)/(1-2x+x 2) 当1x 时 有 11 11x x x += -- (3)3 2 3 2 (1)(133)(136)x G x x x x x -=+--+++ =23423451361015391830x x x x x x x x ++++++++234391830x x x x -----34563610x x x x ----=1 3 1 (1) G x ∴= - 2.10题 +???? ??++++++=n x n x x x H 332010413 2 证明(1) ∑∞ =??? ? ??+==-022)1(n n x n G H x (2) 求H 的表达式。 证明(1) 设H 的第K+1项为h k ，则h k =??? ? ??+33n =1*2*3)1)(2)(3(+++k k k =66 11623+++k k k ， 设G 的前K+1项的和为G k ，则G k = ∑=k k k g 0=???? ??22+??? ? ??23+…+???? ??+22k 而???? ??22+??? ? ??23+…+???? ??+22k =1+22 *3 + 23*4+…+ 2 )1(*)2(++k k =1+21 [3*2+4*3+…+(k+2)(k+1)] =1+ 2 1 (1+ 22+ 32+…+k 2+3+6+…+3k+2+2+…+2) ①{注释：均为k 项，分别为平方数列，等差数列，常数列} =1+21[61k(k+1)(2k+1)+ 2) 1(3k k ++2k] =1+12)1)(2(2++k k k +4 )1(3+k k +k =121212)1(9)1)(2(2++++++k k k k k k =6611623+++k k k = h k ∴H=x G -1 (2) 由H=1+4x+10x 2+20 x 3+…+(3 3 +n ) x n + (1) x 1*2*32*3*4+1*2*33*4*5x 2+…+n x n n n 1 *2*3)1)(2)(3(++++… 对其3次积分得???H =)1(63x x -，对此积分式3次求导得H=((() 1(63 x x - )))’’’。求解完毕。 2.11题 a n =(n+1)2 ,G= ∑∞ =0 n n n x a =1+4x+…(n+1)2x n +…,证明(1-3x+3x 2-x 2 )G 是一个多项式,并求母函数G 。 解: G= ∑∞ =0 n n n x a =∑∞ =+0 2 ) 1(n n x n =∑∞=++0 2 )12(n n x n n ?G =∑∞ =-1 1 2 n n x n x +∑∞ =-0 1 2n n x n x + ∑∞ =0 n n x ① ? G =xG+ 2)1(2x x -+x -11 ?G(1－x)= 2)1(1x x -+ ? G=3 )1(1x x -+ 即为所求 (1－3x ＋3x 2—x 2)=(1－x)3 ∴(1－3x ＋3x 2 —x 2 )G =(1－x)3 G =(1－x)3 3 )1(1 x x -+=x+1 求解完毕。 ①说明：可以由 ∑∞ =-1 1 2n n x n = ∑∞ =+0 2 ) 1(n n x n 2.12题 已知a n =∑+=1 1 2 n k k , 3 )1(1x x -+=∑∞ =+02)1(n n x n ,求序列{ a n }的母函数。 解：设序列{ a n }的母函数为G(x), 则G(x)= a 0+a 1x+a 2x+…+ a n x n + a 1+n x 1 +n +… a n =∑+=1 1 2n k k =1+22+32+…+n 2+(n+1)2 ∴G(x)=1+(1+22)x+(1+22+32)x 2+…+(1+22+32+…+n 2+(n+1)2) x n +… =1+x+ x 2 +…x n +… +22 x(1+x+ x 2 +…x n +…) +32 x 2 (1+x+ x 2 +…x n +…)+… +(n+1)2 x n (1+x+ x 2 +…x n +…)+…. = (1+x+ x 2 +…x n +…)(1+22 x+32 x 2 +…+n 2 x 1 -n + (n+1)2 x n +…) = x -11 ∑∞ =+0 2 ) 1(n n x n 3)1(1x x -+=∑∞ =+02)1(n n x n ∴G=x -113 )1(1x x -+ ?G=4)1(1x x -+ 即为序列{ a n }的母函数。求解完毕。 2.13题 已知2 1 3 34 10 14,(1),{}(1)n n n n k n x x a k n x a x +∞ ==++==+-∑∑求序列的母函数。 解：B(x)=13+23x+33x 2+…… 1: a 0=13 b 0=13 x: a 1=13+23 b 1=23 x 2 : a 2=13+23+33 b 2=33 …… a 0= b 0 a 1= b 0+ b 1 a 2= b 0+ b 1+ b 2 …… A(x)= b 0(1+x+ x 2+……)+ b 1x(1+x+ x 2+……)+ b 2x 2(1+x+ x 2 +……) +…… =(1+x+ x 2 +……)( b 0+ b 1x+ b 2x 2 +……) = x x B -1)(=5 2 ) 1(x 41x x -++ 2.14题 已知2 {},12n x P x x --的母函数为 (a)求01;P P 和 (b) {}n P 求序列 的递推关系 解: 特征多项式 K(x)= x 2-2x-1 x 2 -2x-1=0 解得：r 1=1+2 r 2=1-2 P(x)= )x 2(11+-A + )x 2(11--B A+B=0 -A(1-2)-B(1+2)=1 得：A= 42, B=-4 2 P(x)= 42()x 2(111+- -)x 2(111 --)= 4 2k k k k x ∑∞ =--+ ])21()21[( P n = 4 2[(1+2)n -(1-2)n ] P 0=0, P 1=1 2.15 题 已知{}n a 的母函数为 2 1 ,1x x -+求序列{}n a 的递推关系01,a a 。 解：特征多项式 K(x)= x 2 -x+1 x 2 -x+1=0解得：r 1=21+23i=cos 3π+isin 3π=e i 3π, r 2=21-23i= cos 3π-isin 3 π = e i 3π - A(x)= x 11r A - +x 12r B - A 1+A 2=1, A 1r 2+ A 2r 1=0 解得：A 1=1，A 2= 3 1 a n =A 1cos π3n +A 2sin π3n = cos π3n +3 1sin π3n a 0=1, a 1=1 2.16 题 证明序列??? ??m m ，??? ??+1m m ，??? ??+2m m ，…，?? ? ??+n m m 的母函数为（1-x ）1--m 证明：当m=0时，命题成立。 假设对于m-1，命题成立，即k k k m m X ∑∞ =+--?? ? ??011=（1-x ）m -， 则G m (X)= k k k m m X ∑∞ =+??? ??0=k k k m m X ∑∞=+-??? ??01+k k k m m X ∑∞=+--?? ? ??011=X ?G m (X)+ （1-x ）m - ∴(1-X) ? G m (X)= （1-x ）m -， G m (X)= X -11 () m X -11 =（1-x ）1--m 2.17题 2 2 4 3123 (1) ...()(1)() 3 n n n n G x x n x a G x x ∞ -=+=++++++=-=∑ 已知证明 2 3 (),(1)(1) ()( ),{0,1,2,...}3 n n n n n k n b G a x a k n k c a n ∞ ∞ ==+==++-==∑∑其中 ()32 4 3022 24 n 0() G (1) G 123(1)(1) G (1) 1n n n n n k k k a x x x x n x x x x x ∞ +-=--∞ =??=-= ?? ?=+++ +++ =-=-??±=± ???∑∑证明：由已知所以有又根据牛顿二项式展开定理（）4134 330032 4 30 n 4 1 G (1) k k k k k k n n n x x x x x ∞ ∞ +-+-==∞ +-=????=-== ? ???? ??? =-= ?? ?∑∑∑令则有（）得证 ∑∑=∞=-++==n k n n n k n k x a b 0 n 0 2 )1)(1(a , G 其中）（ x x x a x x n x x k i i n -= =-=++++++=∑=-1) A()B( b )1()1(321G 0 k 22则若：由性质已知证明： ()2i 2 00i 300002 i 4 000 1 A 111A()G g 1(1)11G()C c 1(1)11C() D G d (1)(1)1i i n n n i i n i n h n n h n i i n n n n h x x x x a x x x g a n x x x c h x x ========== =+++-====--=====+--=====+--∑∑∑∑∑∑∑∑∑即即 即 i 000101d c a (1) c a a a =+可将表示成如下形式： ：：120122 (a 2) c a a (a 3) a =++= ：n 012n n c a a a (a n 1) a ++++=+ ：n 0n 0 d (1)(1) 111 a (1)(1)n i i n k c i n i i n i k k n k ====++-++-+=++-∑∑其中（）表示每列上的数值，（）表示（）这个数的个数。所以成立 {} ()(){} ()()n 3n 3330 330 () a n 0,1,2, 11 n 0,1,2, (1) n 0 11 1 1 n n k n n k c k n k k n k ++=+=?? =∈ ??? ?? ++-=∈ ????? =++-== ???∑∑证证明：题目即证当时等式成立 ()()()()1 13233 (2) n m -1 11 11m 2(m-1) 3(m-2) m 1(m 2)(m 1)m 3n m k k m m k n k k m k -==-++=++-=+-=?+?+??++???? === ? ????? ∑∑假设，当时等式成立，即 ！ ()()()()0 (3) n m 11 11 1123(1)(1)1 1112(1)211(1)1 n m k k k n k k m k m m m m m m m m ===++-=++-=?++?+?-+++?=?+?+?-+?++?++?∑∑当时有（）()()()()1 01 112(1) (m 2)(m 1) 12 m k m k k m k m k m k -=-==+-+++ ++++=+-+ ∑∑ ()()()()m 3m 2m 23331 230 1 m 230(m 3)(m 2)(m 1)3(m 2)(m 1)(m 2)(m 1) 332 n m -1 1 (m 2)(m 1) 12m m k m k k m k k m k +++-+=-+=+++++++??????==+=+ ? ? ??????? ?? =+-= ? ??++??+-+=+ ???∑∑！！当时等式成立即所以()()m 330n 3n 3(m 2)(m 1) 2 11 12 3 a m k k m k +=+++?? ++-= ????? = ??? ∑即等式成立 综合（），（），（）得证 2.18题 用母函数法求下列递推函数关系的解. 1212212122()680()14490()90()670()12360 ()250 n n n n n n n n n n n n n n n n a a a a b a a a c a a d a a a e a a a f a a -----------+=++=-=--=-+=-= 22103321443220102010010():680 :680:680)...... 0(())6(())8() (168)()6(6)a x a a a x a a a x a a a A x a a x x A x a x A x x x A x a a x a x a a a x -+=-+=-+=+=----+-+=+-=+-解： 102000100110011000101(6)(14)(12)()(42) ()1681214(12)(14)(12)(14) 1 622(6)41(4) 11(42)6242242 1 64(61142 n a a a x A B A x B x A B A B A x x x x x x x x x a A B a a a a a a a a a a A B a a a a a a a B +--+-+-+= =+== -+------+=-? ---===-?-+=---? --==所以所以有解之得:A=001100110 011001100001100)421(2) 24221(4)21(2) 2 111111()(4)(2)(4)(2)(2)(4)2122142211 [(4)2(2)4(2)22n n n n n n n a a a a a A a a B a a A x a a a a a a x a a x x x a a a a n ∞∞ ==∞ =--==---?=-??? ?=-??=-+-?=-?+-?--=-?+-?≥∑∑∑因此故此 221033214432():14490 :14490:14490):...... b x a a a x a a a x a a a ++=++=++=+解： 2010(())14(())49()0A x a a x x A x a x A x --+-+= 20100100102220 1010001010(1(449)()14(14)(14)(17)()7()11449(17)(17)(17)(17) 714111 (14)(14)(7) 777 x x A x a a x a x a a a x a a a x A B A x B A B Ax A x x x x x x x A B a A a a A a a B a A a a a a a ++=++=++++++++==+== +++++++=?? =+?=+=-=-+=-+所以所以有故此 10102 101000 101000011111()(14)(7)7177(17)111(14)(7)(7)()(7) 2.16) 17711 [(14)(7)(1)](1)77 71 [()](1)77 n n n n n n n n n n A x a a a a x x n a a x a a a a a a n x a a a a n ∞∞==∞ == +-++++=+--+-=+-++-=-+-∑∑∑n 故此(参见题所以 220331442():90 :90:90):...... c x a a x a a x a a -=-=-=+解： 201012(())9()0 (19)()0 (13)(13)()(33)()191313(13)(13)(13)(13) A x a a x x A x x A x a a x A B A x B x A B A B x A x x x x x x x x ---=-=+++-++-==+== --+-+-+所以有于是 0 1 01 010********* 010101010333311 26 1111 2626 112611261111111111()()()()3()(1)3261326132626n n n n n n A B a A B a x A a a A a a B a A a a a a a A a a B a a A x a a a a a a x a a x x x ∞ =+=?? -=?+=+=+=-=--=-?=+??? ?=-?? =++-=++---+∑①故此有②②①有6于是有③ 将③代入①有④ 即故此001010 01011111 [()()(1)]326261111 [()(1)()]3(2) 2626 n n n n n n n a a a a x a a a a a n ∞=∞ ==++--?=++--?≥∑∑n 所以 221033214432():670 :670:670):...... d x a a a x a a a x a a a --=--=--=+解： 201020100102010 10 (())6(())7()0(167)()6(6)(1)(17)()(7)()167(17)1(17)(1)(17)(1) 76781 8 A x a a x x A x a x A x x x A x a a x a x a a a x A B A x B x A B A B x A x x x x x x x x x A B a A B a a A a a A -----=--=+-+-++-++-==+== ---+-+-++=?? -=-?+?=+=所以因而①故此有②②①得于是有01()a a +③ 0001010101010101010001010 011188 1818111888118818()(7)()(7)111()()(7)()7(7)(1)1718[()7(7)(1)]()7n n n n n n n n n n n n B a A a a a a a A a a B a a A x a a a a a a x a a x x x a a a a x a a a ∞∞ ==∞ ==-=-+=-?=+?? =-?? =++-=++---+=+?+--=+?∑∑∑将③代入①有④ 从而故此所以0118 (7)(1)(2) n a a n +--≥ 221033214 432():12360 :12360:12360) :...... e x a a a x a a a x a a a -+=-+=-+=+解： 20102 010(())12(())36()0 (11236)()12A x a a x x A x a x A x x x A x a a a x ----+=-+=+-于是 010222 2 10(12)(16)()6()(11236)(16)(16)(16)(16)612a a a x A B A x B A B Ax A x x x x x x x A B a A a a +--++-= =+==-+----+=?? -=-?从而①故有② 01 000101 0101 1 26 11 (2)66 12616A a a B a A a a a a a A a a B a a =-=-=--=-+? =-??? ?=-+?? 由②有③ 代入③就有④即 01010012 000101001000011111111()(2)()(2)6()()616166(16)66111[(2)()(1)]6[()]66661 [()]6(2) 6 n n n n n n n n n n n n n n n A x a a a a a x a a x x x a a a a n x a a a n x a a a a n n ∞∞==∞ ∞ ==+=-?+-+?=-+-+--=-+-++?=+-+=+-+?≥∑∑∑∑从而所以 2203314 42():250 :250:250) :...... f x a a x a a x a a -=-=-=+解： 2012 01())25()0125)()A x a a x x A x x A x a a x ---=-=+(故此（ 0122 2 010101010101001212(15)(15)()(55)()1251515125125110155101111111111()()()()5(210152101521021n n n a a x A B A x B x A B A B x A x x x x x x A a a A B a A B a B a a A x a a a a a a x a x x ∞=+++-++-= =+==--+--?=+?+=?? ?? -=??=-?? =++-=++--+∑从而故此于是有从而1001010 )(1)501111 [()5()(1)5](2) 210210n n n n n n n n n n a x a a a a x x n ∞ =∞ =-=++--≥∑∑ 作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明： 习题二证明：在一个至少有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个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有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个相同种类的水果。 第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 排列组合》 一、排列与组合 1. 从9 人中选派2 人参加某一活动，有多少种不同选法？ 2. 从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法？ 3. 现从男、女8名学生干部中选出2名男同学和1 名女同学分别参加全校“资源”、“生态” 和“环保”三个夏令营活动，已知共有90 种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4. 一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58 种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 A.12 个 B.13 个 C.14 个 D.15 个 5．用0，1 ，2，3，4，5 这六个数字， （1 ）可以组成多少个数字不重复的三位数？ （2）可以组成多少个数字允许重复的三位数？ （3）可以组成多少个数字不允许重复的三位数的奇数？ （4）可以组成多少个数字不重复的小于1000 的自然数？ （5）可以组成多少个大于3000，小于5421 的数字不重复的四位数？ 二、注意附加条件 1.6 人排成一列（1 ）甲乙必须站两端，有多少种不同排法？ （2）甲乙必须站两端，丙站中间，有多少种不同排法？ 2. 由1 、2、3、4、5、6 六个数字可组成多少个无重复数字且是6 的倍数的五位数？ 3. 由数字1 ，2，3，4，5，6，7 所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379 个数是 A.3761 B.4175 C.5132 D.6157 4. 设有编号为1、2、3、4、5 的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在 ?1.证：对n 用归纳法。先证可表示性： 当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立， 设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性： 设n=∑a i ·i!=∑b i ·i!, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证： 组合意义： 等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证： 设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑 一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒， 要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而 要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第1步从特定引擎对面的3个中取1个有 C(3,1)种取法，第2步从特定引擎一边的2个中 取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现 了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后 按乘法法则放到一起，而男女分别在前面,应该 再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下， 根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一 个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。 组合数学课后标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题二证明：在一个至少有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个相同种类的水果。 李凡长版-组合数学课后习题答案-习题3 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17 组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k 组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。 第二章 容斥原理与鸽巢原理 1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000. 记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有： |A 1| = L 10000/4」=2500, |A 2| = L 10000/5」=2000, |A 3| = L 10000/7」=1428, 于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为 | A 1∩A 2|=L 10000/20」=500； 同理， | A 1∩A 3|=L 10000/28」=357, | A 2∩A 3|=L 10000/35」=285, A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为 | A 1∩A 2∩A 3|=L 10000/140」= 71. 由容斥原理知，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 5143 2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除 的整数集合，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - ||321A A A ?? - 2 = 10000 - L 10000/140」- 2 = 9927 3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多 少个？ 解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除， 也能被7整除的整数集。则： |A 1| = L 10000/20」= 500, |A 2| = L 10000/140」= 71, 所以1与10000之间能被4和5整除但不能被7整除的整数的个数为：500-71=429。 4、计算集合{2·a, 3·b, 2·c, 4·d }的5组合数. 解 令S ∞={∞·a, ∞·b,∞·c,∞·d}，则S 的5组合数为()1455 -+ = 56 设集合A 是S ∞的5组合全体，则|A|＝56，现在要求在5组合中的a 的个数小于等 于2，b 的个数小于等于3，c 的个数小于等于2，d 的个数小于等于4的组合数. 定义性质集合P={P 1,P 2,P 3,P 4},其中： P 1：5组合中a 的个数大于等于3； P 2：5组合中b 的个数大于等于4； P 3：5组合中c 的个数大于等于3； P 4：5组合中d 的个数大于等于5. 将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由 S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142 2 -+ = 10. 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 第6章 容斥原理及应用 6.7 练习题 3、求出从1到10000既不是完全平方数也不是完全立方数的整数个数。 解：∵100001002=,9261213=,10648223= ∴从1到10000，共有100个平方数，21个立方数 又∵409646=，1562556= ∴从1到10000，共有4个6次方数，也就是共有4个数既是平方数又是立方数 计算：10000-100-21+4=9883 ∴从1到10000既不是完全平方数也不是完全立方数的整数有9883个 □ 4、确定多重集{}d c b a S ????=5,4,34，的12-组合的个数。 解：设T ：{}d c b a S ?∞?∞?∞?∞=,,,*的所有12-组合 1A ：a 的个数大于4的12-组合 2A ：b 的个数大于3的12-组合 3A ：c 的个数大于4的12-组合 4A ：d 的个数大于5的12-组合 要求的是： 4321A A A A ??? = T )(4321A A A A +++- )(434232413121A A A A A A A A A A A A ?+?+?+?+?+?+ )(432431421321A A A A A A A A A A A A ??+??+??+??- )(4321A A A A ???+ T =??? ? ??-+121412=455 1A =???? ??-+7147=120 2A =???? ??-+8148=165 3A =???? ??-+7147=120 4A =??? ? ??-+6146=84 21A A ?=???? ??-+3143=20 31A A ?=???? ??-+2142=10 41A A ?=???? ??-+1141=4 32A A ?=???? ??-+3143=20 42A A ?=???? ??-+2142=10 43A A ?=???? ??-+1141=4 321A A A ??=421A A A ??=431A A A ??=432A A A ??=4321A A A A ???=0 455-（120+165+120+84）+（20+10+4+20+10+4）=34 ∴多重集{}d c b a S ????=5,4,34，的12-组合的个数是34 □ 9、确定方程 204321=+++x x x x 满足 611≤≤x ，702≤≤x ，843≤≤x ，624≤≤x 的整数解的个数。 解：设 116x y -=， 227x y -=， 338x y -=， 446x y -= 则原方程等价于 确定方程 74321=+++y y y y 满足 501≤≤y ， 702≤≤y ， 403≤≤y ， 404≤≤y 的整数解的个数。 设S ：74321=+++y y y y 的所有非负整数解的集合 1A ：74321=+++y y y y 的所有满足61≥y 的非负整数解的集合 2A ：74321=+++y y y y 的所有满足82≥y 的非负整数解的集合 3A ：74321=+++y y y y 的所有满足53≥y 的非负整数解的集合 4A ：74321=+++y y y y 的所有满足54≥y 的非负整数解的集合 若j i ≠，则?=?j i A A ,那么要求的是： 1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5) 第一章： 1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。 解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？ 解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。 1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有10 ! 10 种方式。 两人坐在一起的方式数为9 ! 92? ,故两人不坐在一起的方式数为：9！-2*8！。 1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？ 解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求： x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=??? ? ??-+=515456 (2)分为求： x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35 x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20 x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10 x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4 x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1 将它们相加即得， F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。 第二章： 2.3. 在边长为1的正三角形任意放置5个点，则其中至少有两个点的距离≤1/2。 解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离≤1/2。 1/2 1/2 1/2 第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?? ???=41(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=（2 11x -）2 . （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ????????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1) x x -=0k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= ()1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得 1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|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题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？ 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！ n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１ 1.7题 试证：)2()2)(1(n n n ++被2n 除尽。 证明：因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。组合数学课后答案
(完整word版)组合数学课后答案
组合数学作业答案
完整版排列组合练习题及答案
清华组合数学()习题答案
组合数学课后标准答案
李凡长版-组合数学课后习题答案-习题3
组合数学题目及标准答案
组合数学作业答案1-2章2016
李凡长版组合数学课后习题标准答案习题
组合数学 课后答案
组合数学6章作业答案
李凡长版 组合数学课后习题答案 习题1
组合数学习题解答
李凡长版 组合数学课后习题答案习题4
组合数学参考答案(卢开澄第四版) - 修改版
相关主题
文本预览