一个组合问题

mathe

记$C_n^m$表示从n个不同的球中选择m个方案数目.(当n<m时为0,而且$C_0^0=1$)
p为素数
求证:
$C_n^m-=C_{n%p}^{m%p}C_{[n/p]}^{[m/p]}\quad (mod p)$
其中$a%b$表示a关于b的余数(范围在0到b-1之间),$[x]$表示不超过x的最大整数

gxqcn

比较纳闷：有“同余”符号，但却不知“模”是多少？

gxqcn

难道这里的 $-=$ 表示“恒等”？

令 $n=12, m=5, p=7$, 则：
左边$=C_12^5$,
右边$=C_5^5C_2^1=2$，
也不相等啊？

mathe

漏了mod p了,已添加
不过你上面的例子中,p=7时,右边是$C_5^5C_1^0=1$而不是2

gxqcn

数论中一般的高斯函数定义为：用 $[x]$ 表示不超过 $x$  的最大整数；
你的主题帖中，与之并不同：$[x]$ 表示不小于 $x$ 的最大整数。

估计是“笔误”吧？

mathe

错误太多了

〇〇

为什么要强调p为素数？

无心人

因为小肚子是素的

056254628

可以用母函数来证明：
设 $n%p =b_1,\quad[n/p]=k_1$
      $m%p =b_2,\quad[m/p]=k_2$
$(1+x)^n=(1+x)^(k_1*p+b_1)=(1+x)^(k_1*p)*(1+x)^(b_1)=(\sum_{i=0}^{p}C_p^ix^i)^(k_1)*(1+x)^(b_1)$

因为p为素数，所以 $(\sum_{i=0}^{p}C_p^ix^i)^(k_1)*(1+x)^(b_1) -= (1+x^p)^(k_1)*(1+x)^(b_1)\quad (mod p) $
即  $(1+x)^n -= (1+x^p)^(k_1)*(1+x)^(b_1)\quad (mod p) $

式子左边$x^m$的系数是$C_n^m$,式子右边$x^m$的系数是$C_(k_1)^(k_2)*C_(b_1)^(b_2)$

证毕。

mathe

发现这个就是组合里面的 <A href="http://en.wikipedia.org/wiki/Lucas'_theorem" target="_blank">Lucas定理</A>