P(k,r)
0 k m X
如上图所示
?r?k????k?表示（0，0）点到P点的路径数； ??P点到P’点只有一步；
?n?m?m?k??n?k????m?k??表示P’点到B点的路径数; ?m?k?=??????n?r?1????m?表示（0，0）点到B点的路径数。 ??所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。
M0?+???r?k??n?k????k?*1*??m?k??=?????0M?n??r??n?1??r?1??n?2??r?2???m????0??+??m?1????1??+??m?2????2??+??????????????n?m??r?m??n?r?1?????=? ??????0??m??m?1.38题（王振华）
?r??r?1??r?2??n??n?1?给出??r?????r?????r???????r?????r?1??的组合意义。
??????????解：
设A={a1,a2,….,an?r?1 ,……,an?1 },从A中取r+1个元素组合成C，考虑以下n-r+1种情况：
?n?（1） a1∈C，则A需要从A\\{a1}中取r个配合，构成C，共??r??种可能
??（2） a1?c，a2?c,则需要从A\\{a1,a2} 中取r-1个，加上a2构成C，共??中可能
??
(n-r)a1,a2,...,an?r?1?C，an?r?C，则需从A\\{a1,a2,...,an?r}中取r个组合，再加上
?n?1????r??r?1?
an?r构成C，共??r??种可能。
??
?r?(n?r?1)a1,a2,...,an?r?C,这时只有??r??=1种可能。
??故??r??+?+??r??+??r?1?? ?r??+??r??+??r??=?
????????????（法二）C(n+1,r+1)是指从n+1个元素a1, a2,?,an+1中任取r+1个进行组合的方案数。
左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an,则方案数为C(n-1,r).若不选an+1,an,?ar+2,则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。 1.39 题（王居柱）
n
证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+?+C(m,n)C(m-n,0)=2C(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)
由(x?y)n=C(n,0)x +C(n,1)xn?1y+C(n,2)xn?2y2+?+C(n,n)yn 令x=y=1
可得 C(n,0) +C(n,1) +C(n,2) +?+C(n,n)=2 左边=2C(m,n)=右边 命题得证。 1.40题（王健）
从n个人中选r个围成一圆圈，问有多少种不同的方案？ 解：
圆排列:共有P(n,r)/r种不同的方案。 1.41 题（孙明柱）
分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。 解：
利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号， 生成已知排列序号算法：
设 int M为每一排列的对应序号初始时： P1_P2_...Pi-1_Pi_Pi+1_...Pn_ (其中P1_
I. 满足关系式Pj-1 n ?n??n?1??n?2??r?1??r??n?1? nnII. 满足关系式Pi-1 III. 使Pi-1与 Pj 互换得(p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_ IV. (p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_ 中的Pi_Pi+1_...Pn_部分的顺序逆转，得下一排列。 V. 判断(p_)排列是否与给定排列相同 ，相同则输出M， ELSE M=M+1 GOTO Ι （2）给定序列号计算排列算法： 设 Int M为每一排列的对应序号，M=N （N为给定序号） 设 Int K为循环次数 FOR （K=1；K++；K <=N ） { 满足关系式Pj-1 (p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_ 中的Pi_Pi+1_...Pn_部分的顺序逆转，得下 一排列 } 输出(p_)排列。 1.42题（李拂晓） 1：给定排列求相应序号： 设 Int I为每一排列的对应序号 I=1 （初始化） 假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列 S1： A[1]?1 i从2到n作 始 A[i]?i，D[i]?i，E[i]??1 终；S2： q?0； 判断A[1：n]是否与B[1：n]相等 若相等则输出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 终 终 终 2：给定序号求相应排列： 设 Int I为每一排列的对应序号 I=1 （初始化） M为给定序列号假定A[1：n]和E[2：n]；D[2：n]；都是整数数组 M=N