恒等式证明

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<n时，上式为0，mathe给的题目正是紧紧的利用了这一特点，就结合牛顿二项公式加入了一个实数x，。。。

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

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