作业帮求证:Cmn(组合)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数Cmn(组合,因为不能打上下标只能这样了。)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/03 23:28:14
求证:Cmn(组合)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数Cmn(组合,因为不能打上下标只能这样了。)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数
求证:Cmn(组合)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数
Cmn(组合,因为不能打上下标只能这样了。)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数
求证:Cmn(组合)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数Cmn(组合,因为不能打上下标只能这样了。)(m=1~n) 当且仅当n=2^k-1(k为正整数)时全部为奇数
只想到一种方法,思路很简单,但过程有些繁琐,某些步骤没写清楚的话pm我就是了.
通过组合数公式,可以知道这个命题相当于证明：对于任意m属于1到n-1都有Cmn为偶数当且仅当n=2^k.
首先,假设n=2^k*C,C为奇数且不为1.取m=2^k.
Cmn=n!/m!(n-m)!.Cmn里2的次数为
p(2)=求和[n/2^P]-求和[m/2^P]-求和[(n-m)/2^P].每个求和都是p从1到正无穷,但因为有取整符号在,所以其实是有限项的和.
用k表示n和m,然后把每一个求和分成p从1到k,以及p>k.具体过程就不写了,写出来也看不清.
化简后最后剩下
p(2)=([C/2]+[C/4]+...)-([(C-1)/2]+[(C-1)/4]+...).
因为C是奇数,所以对应的项抵消,p(2)=0.
因此Cmn为奇数.这就证明了n=2^k是必要条件.
另一方面,因为C24、C14和C34都是偶数,所以只要证明对于Cmn整除Cm(2n),就能利用对k归纳,证明对于n=2^k,m从1到n-1,Cmn永远是偶数.
两者相除,并设l=n-m,得到(2n)!*l!/(n!*(m+l)!).
考虑这个式子里质数p的次数,就有
p(p)=求和[2n/p^s]+求和[l/p^s]-求和[n/p^s]-求和[(n+l)/p^s].
这里是关于s求和.
要证明p(p)>=0,只需证明对于任意s,[2n/p^s]+[l/p^s]-[n/p^s]-[(m+l)/p^s]>=0即可.
设n/p^s=a,l/p^s=b,化简成
[2a]+[b]-[a]-[a+b],并且a>=b.
显然可以假设a,b都属于[0,1],否则减去整数部分.
这样就变成[2a]-[a+b].因为2a>=a+b,所以原式大于等于0.
这样就证明了对于任意p,p(p)>=0,也就是说Cmn整除Cm(2n).
因此对于n=2^k,m不等于0或n,利用Cmn=C(n-m)n,可以将Cmn化成C41或C42的倍数,这就说明Cmn为偶数.
这样,n=2^k的充分性也得到证明,全部证明完成.