《武汉工程大学学报》  2008年01期 120-121   出版日期：2008-01-30   ISSN:1674-2869   CN:42-1779/TQ

---

广义第二类Stirling数及其性质


0引言Stirling数在组合数学、计算数学等方面有重要应用，它们有许多有趣的性质［1~5］．本文对第二类Stirling数进行了推广，得到了广义第二类Stirling数．证明了广义第二类Stirling数的一些基本性质，并利用所得结果，对一些组合计数问题进行了研究．1广义第二类Stirling数及其性质定义1.1设集合A有n个元素，将A分成k类且每类中至少有r（n≥kr）个元素，称为A的k-r分划．A的所有k-r分划方法的数目记为S2(n,k,r)，并称之为广义第二类Stirling数．显然，当r=1时，S2(n,k,1)即为第二类Stirling数，因此以后记S2(n,k,1)=S2(n,k)．定理1.1设集合A有n个元素，则A的广义第二类stirling数满足：
S2(n,k,r)=n-1
r-1S2(n-r,k-1,r)+kS2(n-1,k,r),n>kr,k≥2,r≥1(1)证将A的k-r分划分为如下两类：a．A的k-r分划的子集中含a1且恰好有r个元素．先从{a2,a3,…,an}中取r-1个元素，有n-1
r-1种取法，将a1加入到所取r-1个元素中，再对剩下的n-r个元素分成k-1类且每类至少有r个元，有S2(n-r,k-1,r)种．由乘法原理知A的k-r分划中含a1且恰好r个元的子集的分划数为n-1
r-1S2(n-r,k-1,r)．b．含a1且多于r个元的子集的A的k-r分划，先将a1从A中拿出，即对{a2,a3,…,an}进行k-r分划，分划数为S2(n-1,k,r)，再将a1放入分划的子集（类）中，有k种放法，故含a1且多于r个元的A的k-r分划数为kS2(n-1,k,r)．由加法原理知A的k-r分划数为：n-1
r-1S2(n-r,k-1,r)+kS2(n-1,k,r)即（1）式成立．特别地，当r=1时有，
S2(n,k)=S2(n-1,k-1)+kS2(n-1,k)［1］（2）定理1.2S2(n,k,r)=∑n-rm=0n-1
mS2(m,k-1,r),n>kr,k≥2,r≥1（3）证设A={a1,a2,…,an}，对A进行k-r分划．按含a1的子集元素的个数分类进行计数．其中含a1的子集有p（r≤p≤n-(k-1)r）个元素的方案数如下计算：先从除a1以外的元素{a2,a3,…,an}中取p-1个（与a1构成含a1且有p个元素的子集），有n-1
p-1=n-1
n-p种，再对另外n-p个元素分成k-1个子集且每个子集的元素至少为p个，有S2(n-p,k-1,r)种，于是子集含a1且元素为p个的分划方案数为n-1
n-pS2(n-p,k-1,r)种.由加法原理，A的所有k-r分划数共有：
S2(n,k,r)=∑n-(k-1)rp=rn-1
n-pS2(n-p,k-1,r)=∑n-rm=(k-1)rn-1
mS2(m,k-1,r)注意到当m<(k-1)r时有S2(m,k-1,r)=0，从而有：
S2(n,k,r)=∑n-rm=0n-1
mS2(m,k-1,r)当r=1时，（3）式成为：
S2(n,k)=∑n-1m=0n-1
mS2(m,k)这便是第二类Stirling数的基本公式之一［2］．第1期胡端平：广义第二类Stirling数及其性质
武汉工程大学学报第30卷
2广义第二类Stirling数与分配计
数分球入盒是典型的组合中的分配问题．我们知道，将n个可辨的球放入k个不同的盒中，无一空盒的分配方案数为k！S2(n,k) ［2］，k≤n．定理2.1将n个可辨的球放入k个可辨的盒中（盒内无序），每盒至少r个球，其方案数为q（n，k，r），则q（n，k，r）=k!S2(n,k,r)（4）证先将n个球分成k类且每类中至少r个球，有S2(n,k,r)种分法；然后将每类分别各放入1盒内，有k！种放法．从而满足条件的分配方案数为k！S2(n,k,r)，即证（4）．由（1）式有
k!S2(n,k,r)=n-1
r-1k!S2(n-r,k-1,r)+kk!S2(n-1,k,r)从而由（4）式有：推论2.1
q（n，k，r）=kn-1
r-1q(n-r,k-1,r)+
kq(n-1,k,r)（5）当r=1时有，q(n,k)=kq(n-1,k-1)+kq(n-1,k)［3］ 这里q(n,k)=q(n,k,1).同理，由（3）式，我们有：推论2.2
q(n,k,r)=k∑n-rm=0n-1
mq(n,k-1,r)