第一章习题
1.1,从{1,2,...,50}中找一双数{a,b},使其满足：
(1), a b 5 (2), a b 5
求这样的一对数的组合数。 解：1 分三部分，1-5，6-45，46-50 [C(5,1)+C(40,1)×2+C(5,1)]/2 解：2 分三部分，1-5，6-45，46-50 [5+6+7+8+9+C(40,1)×10+9+8+7+6+5]/2
000000到000999左数第4位的0出现了102次, 000000到000099左数第5位的0出现了10次, 000000到000009左数第6位的0出现了1次。
因此不合法的0的个数为105+104+103+102+101+1=111111， 不合法的应该去掉，再加整数1000000中的6个0，这样，从1到 1000000的整数中0出现的次数为6×105-111111+6=488895。
问题：在去掉多余的零的过程中，多减去了一部分，例如： 000000这种情况在每次减的过程中都出现。
1.16、n个完全一样的球放到r个有标志的盒中，无一空盒， 试问有多少种方案？
取r个球每盒放一个，然后n-r个放入r个不同盒中，同充许空盒 的放法。
C(r+n-r-1,n-r)=C(n-1,n-r)=C(n-1,r-1)
(b)把n个女生作为一个整体来看待。n!(m+1)! (c)男生A与B作为一个整体，(m+n-1)!*2
1.5,求3000到8000之间的奇整数的数目，而且没有相同的数字。 解： C(5,1)C(10,1)C(10,1)C(5,1)=2500
C(3,1)C(4,1)C(8,1)C(7,1)+ C(2,1)C(5,1)C(8,1)C(7,1) =672+560=1232 1.6,计算1×1!+2×2!+3×3!+n×n! 解： (n+1)!-1,迭代。 1.7,试证(n+1)(n+2)...(2n)能被2n除尽。 解： =(2n)!!(2n-1)!!/n!=2nn!(2n-1)!!/n! =2n(2n-1)!!
1.13、有n个不同的整数，从中取出两组来，要求第1组的最 小数大于另一组的最大数。
设取的第一组数有a个,第二组有b个,而要求第一组数中最小 数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从 大到小取a个作为第一组,剩余的为第二组。此时方案数为 C(n,m)。从m个数中取第一组数共有m-1中取法。 总的方案数为
组合意义： 从n个不同的球中取出的r+1个，要求指定第一个球，有两种
方式：
1、等式左边：n个不同的球，先任取出1个，再从余下的n-
1个中取r个；
2、等式右边：n个不同球中任意取出r+1个，并指定其中任
意一个为第一个。 显然两种方案数相同。
1.12 试证等式：
n
kC(n, k) n2n1
k 1
用多项式(1+x)n证明，求导
再证表示的唯一性： 设n=∑ai·i!=∑bi·i!,
令j min{ i ai bi}
aii! bii!
i j
i j
两边同时除以( j 1)!, 得余数a j j! bj j!
也就是a j! bj!,矛盾。
1.11 证明下式，并给出组合解释
nC(n 1, r) (r 1)C(n, r 1)
1.18、8个盒子排成一列，5个有标志的球放到盒子中，每盒 最多放一个球，要求空盒不相邻，问有多少种排列方案？
5!×6×5×4
1.19、n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问 不存在两个1相邻的符号串的数目？
(m+1)*m*...*(m-n+2)/n!=C(m+1,n)
1.20、甲单位有10个男同志，4个女同志，乙单位有15个男同 志，10个女同志，由他们产生一个7人的代表团，要求其中甲单 位占4人，面且7人中男同志5位，试问有多少种方案？
n
(m 1)C(n, m) 要求引擎的点火的次序两 排交错开来，试求从一特定引擎开始点火有多少种方案。
解： ⊙ ⊙ ⊙ ⊙⊙⊙
第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.8、求1040和2030的公因数数目。 解：
等价于求(2×5)40和(2×2×5)30 的公因数数目。 C(40,1)+C(40,1)C(30,1)+C(30,1)+1=40+1200+30=1271 C(41,1)C(31,1)=1271
1.9、试证n2的整除数的数目是奇数。
n p1a1 p2a 2 ... pm am n2 p12a1 p2 2a 2 ... pm 2am
1.3,m个男生，n个女生，排成一行，其中m,n都是正整数，若 (a)男生不相邻（m≤n+1)； (b)n个女生形成一个整体； (c)男生A与女生B排在一起。
解： (a)首先女生的全排列有n!个，那么第一个男生有n+1个位置 可选第二个男生有n个位置，...，第m个男生有n-m+2个位置可选。 男生不相邻的排列数有n!(n+1)!/(n-m+1)!
习题：1.15试求从1到1000000的整数中，0出现的次数。 解：先将1到999999的整数都看作6位数,例如2就看作是
000002，这样从000000到999999。0出现了多少次呢？ 6×105，某一位取0，其它各位任取。 0出现在最前面的次数应该从中去掉 000000到999999中最左1位的0出现了105次， 000000到099999中左数第2位的0出现了104次， 000000到009999左数第3位的0出现了103次,
所有的组合数都是偶数，最后再加上1，偶数加1是奇数
1.10 证明任一正整数n可惟一地表示成：
n a1i!,0 ai i, i 1 i 1
先证可表示性： 当n=0,1时，命题成立。 假设对小于n的非负整数，命题成立。 对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k! 由假设对n-k!,命题成立， 设n-k!=∑ai·i!，其中ak≤k-1, n=∑ai·i!+k!，命题成立。