一个组合问题

mathe

记$C_n^m$表示从n个不同的球中选择m个方案数目.(当n

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

发现这个就是组合里面的 Lucas定理