斯特林数和自然数前m项n次方的求和公式.doc

斯特林数和自然数前m项n次方的求和公式将 个元素，分成 个非空子集，不同的分配方法种数，称为斯特林数（Stirling Number），记为，。例如，将4个物体分成3个非空子集，有下列6种方法：，。所以， 。 斯特林数的值列表如下：123456789112113131417615115251016131906515171633013501402118112796617011050266281912553025777069512646462361容易看出，有 ， 。定理1 当 时，有 。证 把个元素分成个非空子集，有种不同分法。把个元素分成个非空子集，也可以这样考虑：或者将第个元素单独作为1个子集，其余个元素分成个非空子集，这种情况下有种不同做法；或者先将前个元素分成个非空子集，有种分法，再将第个元素插入这个子集，有种选择，这种情况下有种不同做法。所以共有种分法。两种考虑，结果应该是一样的，因此有 。如果规定当或时，则公式 对任何正整数和任何整数都成立。定理2 对任何整数 和 ，有 。证 用数学归纳法证明。（1）当 时， ，公式成立。（2）设已知对某个正整数 ，公式成立，下面看 时的情形： ，可见 时公式也成立。（3）所以，对任何正整数 ，公式都成立。 例如，有 ， , , 。定理3 当 时，有 。证 将个元素分配到个不同的格子中，每个格子可以有多个元素，也可以没有元素，共有种不同分配方法。将个元素分配到个不同的格子中，也可以这样考虑：先将个元素分成个非空子集，有种不同分法，再将这个子集分配到个格子中，每个格子最多只能放一个子集，不同的子集分配在不同的格子中，有种不同分法，共有种不同做法。这里可取中每一个值，所以有 。定理4 对任何正整数 ，有 。证 用数学归纳法证明。（1）当 时， ，定理显然成立。（2）设已知对某个正整数 ，定理成立，下面看 时的情形：，可见当 时，定理也成立。（3）所以，对任何正整数 ，定理都成立。定理5 对任何整数 和 ，有 。证 由定理3可知 ，由定理4可知 ，所以 。 例如，有 ， ， ， ，。 举例： 。一第一类Stirling数s(p,k)s(p,k)的一个的组合学解释是：将p个物体排成k个非空循环排列的方法数。s(p,k)的递推公式：s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1),1=k=1s(p,p)=1,p=0递推关系的说明：考虑第p个物品，p可以单独构成一个非空循环排列，这样前p-1种物品构成k-1个非空循环排列，方法数为s(p-1,k-1)；也可以前p-1种物品构成k个非空循环排列，而第p个物品插入第i个物品的左边，这有(p-1)*s(p-1,k)种方法。二第二类Stirling数S(p,k)S(p,k)的一个组合学解释是：将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1),1=k=0S(p,0)=0 ,p=1递推关系的说明：考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S(p-1,k-1)；也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同。引用Brualdi组合数学里的一段注释“对于熟悉线性代数的读者，解释如下：具有（比如）实系数，最多为p次的那些各项式形成一个p+1维的向量空间。组1，n，n2，.。np和组A(n,0