在{r+1+k+1, ?,n+r+1}这[(n+r+1)-(r+1+k)]=n-k个数中取，故有???n?k??r?k??n?k??n?k?。根据乘????????n?m??m?k??n?k??r?k?法原理，当ir+1=r+1+k时，这样的组合数为?。根据加法?m?k???1???k?????m?k????k??????????原理，对k=0,1,2,?,m作和，就有
?n??r???m????0????????n?1??r?1???m?1????1????????n?2??r?2??n?m??r?m??n?r?1???????????m?2??2??0????m??????m??????????。
注：参见《 Combinatorial Problems and Exercise》 by L.Lovasz 0143.7 L896c
P18-42 (i) P96 P172
(i)The number of those(n+r+1-m)-tuples of{1,2,?,n+r+1}Whose (r?1)stelement is r+k+1is
?r?k??n?k?. Summing for k=0,1,2,?,m,we ??k????m?k??????get the result.
组合意义二：（格路方法）
等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,?,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1)；
等式右端：从点A(-r-1,0)到点B(n-m,m)的路径数。
C (-1, k) D(0, k) A (-r-1, 0) O (0, 0) 第15题图1 ?r??r?1??r?2??n??n?1?1.38 给出????????????????的组合意义.
rrrrr?1??????????[证].组合意义一：
等式右端是从n+r+1个元素a1,a2,?,an?1中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P25等式3的组合意义)：
(1) r+1个元素的组合中含有a1的，相当于从n个元素a2,a3,?,an?1中取r个组合，其组合数为?（即A）。 ????r??n? (2)r+1个元素的组合中不含有a1，但又含有元素a2的。即一个(r-1)-第16题图1
组合。依a1来分，不外乎含a1和不含a1；不含a1的又依a2分，不外乎含a2和不含a2。不含a1而含a2的组合，相当于从n-1个元素a2,a3,?,an?1中取r个元素的组合，然后加上a2【第 16 页 共 129 页】
而成，其组合数为???n?1??即A1?A2。 ??r???(3)r+1个元素的组合中不含a1和a2，但含有元素a3的。即不含a1,a2的依a3来分，不外乎含a3和不含a3。不含a1,a2而含a3的组合，相当于从n-2个元素a4,?,an?1中取出r
?n?2?个元素的组合，然后再加上a3而成，其组合数为??r??即A1?A2?A3。
????取出的r+1个组合元素中不含a1,a2,a3,?,an?r?1，但含有元素an?r的。即不含又依an?r来分，不外乎含有an?r和不含有an?r。不含a1,a2,?,an?r?1a1,a2,a3,?,an?r?1的，
而含an?r的组合，相当于从n-(n-r-1)=r+1个元素an?r,an?r?1,?,an?1中取出r个元素的组合而加上an?r而成，其组合数为???r?1?。 ??(即A1?A2??An?r?1?An?r)r???r?1??r??????r?? r?1????(4)由an?r?1,an?r?2,?,an?1组成的(r+1)-组合的组合数为??(即A1?A2???An?r)。而且
A1?(A1?A2)?(A1?A2?A3)???(A1?A2???An?r?1?An?r)?(A1?A2???An?r?1?An?r)??(即全集)
组合意义二：
等式右端：从n+1个不同元素a1,a2,?,an,an+1,中任选r+1个元素的组合方案数； 等式左端：从n+1个不同元素a1,a2,?,an,an+1,中选取r+1个元素，一定选元素ar+k+1(k=0,1,2,?,n-r)，但是不选元素ar+k+2,?,an,an+1的组合方案数。 1.39 证明
m??m??m??m??m?1??m??m?n?n??????????????????2?? 0n1n?1n0?????????????n?[证].借助P28等式4，可知：???m??m?????n???0?????m??m?r??m??n??????? (n?r) (r=0,1,2,?,n) ??????????r??n?r??n??r??m??n??m??n??????????n??1??n????n?? ????????从而有???m??m?1??m??m?n??m??n??????????1??n?1??n????0?????n????0???????????????m??m???n??n??n??n????????????????2???n??0??1??n??n??(用了P29等式5)
????????????【第 17 页 共 129 页】
组合意义一：
等式右端可看作从m个元素中取出n个元素进行组合。然后对这取出的n个元素进行染色（红，白）的所有方案，它为???m?n?2； ??n??m?），全部染以红色。再从剩??k??等式左端可看作先从m个元素中取出k个元素（个数为??下的(m-k)个元素中取出(n-k)个元素（个数为???m?k?），全部染以白色。根据乘法原理，从??n?k???m??m?k?，????n?k??k????m个元素中取出n个元素，k个染上红色，(n-k)个染上白色的方案数为??k=0,1,2,?,n；
而从m个元素中取出n个元素染以红白两色的方案可分解成有0个，1个，?，n个染以红色的总和。故根据加法原理，17题成立。
组合意义二：
等式右端：将从m个不同的小球中任意选出的n个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；
等式左端：先从m个球中任选k个球放入第一个合子里(k=0,1,2,?,n)，再从剩下的m-k个球中任选n-k个球放入第二个合子里，然后对k从0到n求和，就得到了所有可能的放球方案数。
1.40 从n个人中选r个围成一个圆圈，问有多少种不同的方案？
?a1,a2,?,ar?1,ar??a2,a3,?ar,a1[解].每一个r个人围成的圈（圆排列）a1,a2,?,ar?1,ar?(线排列)?
????????a,a,?a,ar?2r?1?r1即每一个r圈相当于r个r排列。故不同的方案数为N?1rP(n,r)?1n!r(n?r)!
若不计顺逆方向，则为N?12rP(n,r)?12r(n?r)!?n!。
1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法. [解].（略）
1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.
(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. [解].（略）
1.43 对于给定的正整数n，证明，当
【第 18 页 共 129 页】
n?1?n?1或，若n是奇数??22k??时，C(n,k)的最大值.
n?，若n是偶数??2[证] 取C(n,k)与C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。 当k?n/2时，(n-k+1)/k?1，即C(n,k)?C(n,k-1)；
当k?n/2时，(n-k+1)/k?1，即C(n,k)?C(n,k-1)；
因此，得到当k=n/2或最接近n/2时，C(n,k)取得最大值。 1.44 (a) 用组合方法证明
(n)!(n!)n?12(2n)!2n和
(3n)!2?3nn都是整数.
(b) 证明是整数.
[证] (a)考虑2n个不同的球放入n个不同的合子里，每合两个的方案数。这个方案数应该是整数。
对2n个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n个合子内部的排列共重复计算了2n次，故总的重复因子是2n。因此，把2n个不同的球放入n个不同的合子里，每合两个的方案数是
(2n)!2n。所以，
(2n)!2n是整数。
同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。
对3n个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2?3。n个合子内部的排列共重复计算了2n?3n次，故总的重复因子是2n?3n。因此，把3n个不同的球放入n个不同的合子里，每合3个的方案数是数。
(b)考虑n2个不同的球放入n个相同的合子里，每合n个的方案数。这个方案数应该是整数。
对n2个球进行排列的方案数为(n2)!。而把n个球放入同一个合子里不计顺序，重复因子是n!。n个合子内部的排列共重复计算了(n!)次，故重复因子是(n!)。另外，由于n个合子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。因此，把n个不同的球放入n个相同的合子里，每合n个的方案数是是整数。
1.45 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数.
(b) 在3n+1个球中，有n个相同. 求从这3n+1个球中选取n个的方案数.
[解] (a)相当于从n个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出n-m个小球，m=0,1,2,?,n的方案数。
根据加法原理，这个方案数应该是：C(n,0)+ C(n,1)+?+ C(n,n)=2n。
同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。
(b)相当于从2n+1个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出
【第 19 页 共 129 页】
2
n
n
(3n)!2?3nn。所以，
(3n)!2?3nn是整
(n)!(n!)n?12。所以，(n)!n?12(n!)
n-m个小球，m=0,1,2,?,n的方案数。
根据加法原理，这个方案数应该是：C(2n+1,0)+ C(2n+1,1)+?+ C(2n+1,n)。 1.46 证明在由字母表{0, 1, 2}生成的长度为n的字符串中
(a) 0出现偶数次的字符串有
3n?12个；
n?n?n?n?n?2?n?n?q3?1?n??????2?,其中q?2?? (b) ??2???22?2??0??2??q?[证] (a)方法一：采用（串值）数学归纳法
［基始］当n=1时，0出现偶数次，长度为1的字符串有长度为1的字符串）。所证结论成立；
［归纳假设］当n=m(1?m?k)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有
3m3?121=2个（即1和2两个
?12个；
［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：
(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有
3?12k?2=3+1个；
k
(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，
k?k3k?1?3?1?由归纳假设，此种字符串有??3?2??1=2个；
??所以，按加法原理，0出现偶数次，长度为k+1的字符串共有 (3+1)+
k
3?12k=
3k?1?12个。所证结论成立；归纳完毕。
方法二：采用指数型母函数方法
设：an—0出现偶数次，长度为n的字符串的个数，则{an}的指数型母函数
?A(x)??an?0n?2xnn!?x4?(1?xx2!24!?e2x?x66!??)(1?x1!?x22!?x33!??)????e?ee12123x?x?e2x
[(1?3x1!?(3x)2!1!2??(3x)3!23??)?(1?23x1!3!?x322!?x33!??)][(1?1)?(3?1)x(3?1)x2!?(3?1)x??]【第 20 页 共 129 页】