的排列数等于多少？
解：要求y必须在两个x之间，所以符合要求的排列必须有结构“xyxyx”，把“xyxyx”看作一个元素，与a,b,c,d,e,f,排列排列数等于6！。
1—33 已知r,n,k都是正整数,r≥nk,将r个无区别的球放在n个有标志的盒子里,每盒至少k个球,试问有多少种方案?
解: ①先保证每一个盒子至少k个球,因为球无区别,把n个不同盒子每一个盒子放k个球.共kn个.
②问题转化为将(r-nk)个小球放入n个不同盒子,每个盒子可以放任意个球,可以有空盒,根据可从复组合定理可得共(n+r-nk-1,r-nk)=(n+r-nk-1,n-1)
1.34在r，s，t，u，v，w，x，y，z，的排列中求y居于x和z中间的排列数。 解：一共9个位置，y只能放到2到8中间，当x放到第一个位置，y放到第二个位置，其他全排列有7！种方法，第一个位置也可以放z，共有2*7！种方法。y放到第三个位置，y前x有两种选择，y后z有6种选择，其他全排列，所以方法有2*6*6！，总方法有2*2*6*6种方法，以此类推算到y在第5个位置因为后边是对称的。
总数=2*（7！+2*6*6！+3*5*6！+4*4*6！） =72000
1．35 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线交于多少个点？
解： 根据题意，每4个点可得到两条对角线，1个对角线交点，从10个顶点任取4个的方案有C(10,4)种，即交于210个点。
1.36 试证明一个整数是另一个整数的平方的必要条件是除尽它的数的数目是奇数。
答案：
由：
n=p1p2p3..............，其中
a1a2a3p1,p2是质数，a1,a2....是正整数。
则n的因子数有(a1+1)(a2+1)(a3+1)????个。 得 n2=p12a1p22a2p32a3..............，因为(2a1+1),(2a2+1),(2a3+1)???..
都是奇数，
所以 n2的因子数为(2a1+1)(2a2+1)(2a3+1)??.个，也是奇数个。
1.37 给出
?n??r??n?1??r?1??n?2??r?2??n?m??r?m??n?r?1?????????????????????????m?m??0??m?1??1??m?2??2??0??m??? 的组合意义. y 解: A(-1,m) m B(m-n,m)
. . . . . .
C(-r-1,0) -r-1 -1 0 m-n
可看作是格路问题:左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,
再到点B的所有路径。左边所有项的和就是从C点到B点的所有路径数即为右边的意义.
1.38 给出??r????????r?r??r?1??r?2??n??n?1???????...???r??r?????r?1??的组合意义。 ???????解：设A??a1,a2,...,an?r?1,an?1?，从A中取r+1个元素组合成C，考虑以下n-r+1种情况：
（1）a1?C，则A需从A\\?a1?中取r个与a1配合，构成C，共????中可能。
?r??n?（2）a1?C,a2?C，则需从A\\?a1,a2?中取r个，加上a2构成能。
?n?1??C，共??r?种可??（n-r）a1,a2,...,an?r?1,?C,则需从A\\?a1,a2,...,an?r?中取r个组合，再加上a1构成
?r?1??C，共??r???种可能。
?r??r?（n-r+1）a1,a2,...,an?r?1,an?r?C,这时只有????=1种可能。
故??r????????r 1.39
?r??r?1??r?2??n??n?1???????...???r??r?????r?1?? ???????证明:
证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种
放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。
n左式＝n?C(m,k)C(m?k,n?k)k?0??k?0nm!k!(m?k)!(m?n)!(n?k)!m!?n!?(m?k)!??k?0nk!n!(m?n)!(n?k)!m!?n!
??k?0n(m?n)!n!k!(n?k)!n!k!(n?k)!?C(m,n)??k?0n?2C(m,n)?右式证毕。
1.40 从n个人中选出r个围成一个圆圈，问有多少种不同方案。
解：首先从n个人中选出r个有C(n,r)种方案，r个人进行一个圆周排列， 根据圆周排列公式，共有r!\\r种方案，既(r-1)!种方案， 所以根据乘法法则，一共有C(n,r)*(r-1)!种方案。
1.41 分别写出按照字典序，由给定排列计算其对应序号的算法及由给定序号计算其对应的算法。
解：生成所有排列的数组A[][]： S1. A[0][]<-S2. j<-0;
j从0到n，若pS3. i = max{ j | pj?1j?1pp...p<-12?N，LEN=1；
12n?p,则退出；
j?p}；
jS4. h = max{k | pi?1?p}；
kS5.将
和i?1ph 互换的
'1pp...12'n'1'n；
S6.A[LEN][]<- S7.将
''pp...p,LEN++；
12'1''12nip和p互换，得pp...p...p；
inS8.A[LEN]<-
pp...p...p, LEN++,转到S2;
12ni'1''给定排列计算其对应序号的算法 S1. 输入
pp...p；
12nS2.j<-0,j从0到LEN 若A[j][]==
pp...p，则输出j，退出；
12n 否则j++；
由给定序号计算其对应的算法 S1.输入序号j；
S2.输出A[j][]，退出；
1.42（a）按照习题1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法。 解：
S1.若p1p2?pn没有数处于活动状态则结束。
S2.将处于活动状态的各数中值最大者设为m，则m和它的箭头所指一侧相邻的数互换位置，而且比m大的所有数的箭头改变方向，即—>改为<—，<—改为—>。转S1。
（b）写出按照邻位对换法由给定排列生成其下一个排列的算法。 解：
S1.A[i]<—1； S2.i从2到n做
始A[i]<—i，D[i] <—i, E[i] <—-1终； S3.q<—0 i从1到n输出A[i];
S4.k<—n;
S5.若k>1则转S6；
S6.D[k] <—D[k]+E[k],p<—D[k]; S7.若p=k则做E[k] <—-1,转S10； S8.若p=0 则做 始E[k] <—1,q<—q+1转S10终；
S9.p<—p+q，r<—A[p],A[p] <—A[p+1],A[p+1] <—i，转S3; S10.k<—k-1转S5.
1.43证明：考虑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) 当k>n/2时,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。 1.44 （1）用组合方法证明 （2）证明 (n)!2(2n)！（3n）!2n和 2?3nn都是整数。 ?n!?n?1是整数。 证明： （1）设有2n个不同的球放入n个不同的盒子里，每个盒子两个，这个方案数应该是整数。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了(2!)n次，得到的2n个不同球放入n个不同的盒子里，每盒两个的方案数为 (2n)!(2!)n，得证。同理，若有3n 个不同的球，放入n个不同的盒子里，，每个盒子3个球，重复的次数为(3!)n，故方案数为 (3n)!(3!)n?(3n)!(3?2)n?(3n)!3?2nn，得证。 （2）设有n2个不同的球，将他们放入n个相同的盒子，每盒n个球，这个 方案数应该是整数。由（1）可知，将n2个不同的球放入n个不同盒子的方案数为 (n2)!(n!)n，若为相同的n个盒子，则应把n个盒子的排列数去掉，即n！，故n2个 (n)!2不同的球放入n个相同的盒子，每盒n个球的方案数为 ?n!?n?1，证毕。 1.45 （1）在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。 （2） 在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。