内容发布更新时间 : 2024/12/22 9:33:10星期一 下面是文章的全部内容请认真阅读。

S1： A[1]?1 i从2到n作 始 A[i]?i，D[i]?i，E[i]??1 终；S2： q?0； 判断 I 是否与 M 相等 若相等则 i从1到n输出A[i]； 否则I?I?1；S3： k从n降到2作 始 D[k]?D[k]?E[k]; p?D[k]; 若 p?k 则作E[k]?-1; 否则作 始 若p?0 则作 始 E[k]?1, q?q?1 终 否则作 始 p?p?q; r?A[p]; A[p]?A[p?1]; A[p?1]?r; 转S2 终 终 终 （a） 由给定排列生成其下一个排列的算法

从排列 p?p1p2?pn生成下一个排列S1： 若在 p?p1p2?pn 中无一处于活动状态则停止。 求处于活动状态各数中的数值最大者， S2：S3： 比 m 大的数一律改变箭指头向的 转；S1。1.43题（高亮）

对于给定的正整数N，证明，当K=

（N-1）/2或（N+1）/2， 若N是奇数 N/2， 若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

设为m， m 和它箭头所指一侧数相互邻换位置。当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.44题（顿绍坤） （a）用组合方法证明（b）证明

(3n)!(2n)!和都是整数。 2n2n?3n(n!)(n)!2n?1是整数。

解：

(a)

①方法一： 因为：

(2n)!?2n?n!?(2n?1)!!

所以

(2n)!2n?n!?(2n?1)!!??n!?(2n?1)!! nn22n!?(2n?1)!!是整数，因此

(2n)!是整数。 2n方法二：

设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数

(2n)! 2n②若有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。对这3n个球进行排列得到方案数为(3n)!。而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了3！次。得到3n个不同的球放入n个不同的盒子里，每盒三个的方案数

(3n)!(3n)!?nn n(3!)3?2(b) 有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒

子是没有区别的，应该把n个盒子的排列数n!除去。 因此得到(n2)!/(n!)n+1是整数。 1.45题（陈兴）

a）在2n个球中，有n个相同。求从这2n个球中选取n个的方案数 解：有n个相同就有n个不相同

取n个不相同和0个相同的为C(n,n), 取n-1个不相同的球和1个相同的球为C(n,n-1)，

2等等。

所以总的方案数为

C?n,0??C?n,1????C?n,n??2n

(b) 在3n+1个球中，有n个相同。求从这3n+1个球中选取n个的方案数 方法同上，方案数为

C?2n?1,0??C?2n?1,1????C?2n?1,n?

由于C(2

C?2n?1,0??C?2n?1,1????C?2n?1,2n?1??22n?1

则

12n?1C?2n?1,0??C?2n?1,1????C?2n?1,n??2?22n

21.46题（陈兴）

证明在由字母表{0,1,2}生成的长度为n的字符串中.

(a)0出现偶数次的字符串有个；

(b)，其中.

证：(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.47题（顿绍坤）

5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？ 解：

当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。 所以总的方案数为1.48题（高亮）

?C(m,2n)C(2n,n)3n?0q(m?2n)?m?q???

?2?在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？ 解：

转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,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.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得：3*C4?3*C4?30 (2)、m个0产生m-1个空当。 若k为偶数时：

要得到出现“01”与“10”总次数为k，可以先按上题中1的情况讨论，则在m-1个空当中

21k2。分别插入个1即可，也就是Cm?1剩下的1如何插入的问题与书P20页的定理1.2类似(在

2n个不同元素中取r个允许重复的组合，其组合数为（C（n+r-1,r)），在这里无区别的球的个数也就是剩下的1的个数（即n-

kk），盒子的个数也就是插入到m-1个空当中的1的个数(即2kkkn?n?k22C)，则得出剩下的1的插入方法有n?1。即第一种情况的总的插入方法为：Cm?1*Cn?12。

2k?22m?1k?2?22。 n?1n?同理可得，按2的情况讨论后的第二种情况的总的插入方法为：C*C