恒等式证明

mathe

$\sum_{t=0}^n(-1)^tC_n^t(n+x-t)^n=n!$

winxos

原帖由 mathe 于 2009-5-14 17:15 发表 $\sum_{t=0}^n(-1)^tC_n^t(n+x-t)^n=n!$

怎么会有一个`x`在里面呢？是表示任何的数么？

wayne

把$(n+x-t)^n$牛顿展开，设中间变量为k，

winxos

原帖由 wayne 于 2009-5-14 21:25 发表 把$(n+x-t)^n$牛顿展开，设中间变量为k，

wayne兄数学学的很好 上大学后我数学就是完全是学了点自己喜欢的东西，现在还忘记的差不多了

mathe

原帖由 wayne 于 2009-5-14 21:25 发表 把$(n+x-t)^n$牛顿展开，设中间变量为k， 912

$S_k^{(n)}$的值如何计算呢? 这个题目可以直接通过容斥原理来做. 我们先考虑x是正整数的情况,假设现在有n+x个不同的箱子和n个不同的球,那么请问,将这n个球放入这n+x个不同的箱子,而前n个箱子都不空的方法有多少种呢? 显然,这个数目就是n个球的排序数目为n!. 而另外一方面,利用容斥原理,我们知道,n个球放在n+x个箱子中,有$(n+x)^n$种方案 其中,前n个箱子中指定t个箱子空的方案有$(n+x-t)^n$种方案,而n个箱子选择t个箱子有$C_n^t$种选择 根据容斥原理 总方案数就是$\sum_{t=0}^n(-1)^tC_n^t(n+x-t)^n$种方案. 即$n! =\sum_{t=0}^n(-1)^tC_n^t(n+x-t)^n$

wayne

第二类斯特灵数的计算式子见维基：

wayne

http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E7%81%B5%E6%95%B0 其实上面这个式子就是用容斥原理得来的。 另外，S(n,n) = S(n,1) = 1，递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k) 当k>n时，S(n,k)=0,所以就有了我上面的推导，（仅当n=k时，后面的求和项有非零值，此时，x的指数为0）

wayne

反观原题 其实 ，$\sum _{t=0}^n (-1)^t C_n^t(n-t)^k$ 相当于k个不同的球放进n个不同的袋子，不允许有空袋子，有多少种情况 当k

mathe

还有一种方法. 函数f(x)的差分$\Delta f(x)=f(x+1)-f(x)$ 那么容易证明对于最高项系数为$a_0$的n次多项式f(x),$\Delta f(x)$是最高项系数为$na_0$的n-1的多项式 而记$\Delta^{(1)}f(x)=\Delta f(x)$,$\Delta^{(k+1)}f(x)=\Delta\Delta^{(k)}f(x)$ 那么可以让$f(x)=x^n$得出$n! =\Delta^{(n)}f(x)=\sum_{t=0}^n(-1)^tC_n^tf(x+n-t)=\sum_{t=0}^n(-1)^tC_n^t(n+x-t)^n$

wayne

,这是再简洁不过的证法了