论文总字数：5738字

摘 要

第二类Stirling数 的组合意义是把[n]划分成k个非空子集的个数.该论文对第二类Stirling数的一些性质进行证明.给出了 最基本的递推关系公式,再利用递推公式给出了 的一些其它性质.这些性质可以用来解决相关的计数问题.

关键词：第二类Stirling数，子集，集合的划分，组合

Abstract：The combinatorial meaning of the second kind of Stirling number S(n,k) is the number of partitions of [n] into k non-empty subsets. The aim of this thesis is to give proofs of some properties of the Stirling numbers of the second kind. We first give some basic recurrence relations of S(n,k), and then use these recurrence relations to deduce some other properties of them. These properties can be used to solve some enumerating problems.

Keywords：Stirling numbers of the second kind, Subset, Partions of sets, Combinatorics

目 录

1 前言 …………………………………………………………………………… 4

2 第二类Stirling数的概念……………………………………………… 4

3 第二类Stirling数的性质……………………………………………… 5

结论 …………………………………………………………………………………11

参考文献………………………………………………………………………………12

致谢 ………………………………………………………………………………… 13

1 前言

Stirling数的概念由J.Stirling于1730年提出,并且在他的著作《Methodous Differentialis》中首次使用.Stirling数有两种,分别称为第一类Stirling数和第二类Stirling数.1958年,Riordan首先应用S(n,k)来表示第二类Stirling数.第二类Stiring数实际上是n元集合进行拆分,一直以来都是组合数学中的研究对象之一,涉及多个应用方面.许多学者对此进行研究,甚至将其详细分类,得到了非常重要的结论.本文介绍第二类Stirling数的相关性质,即定理的推广证明,进行归纳总结.从组合意义上,研究第二类Stirling数可以解决很多重要的问题,是值得深入研究的.

2 第二类Stirling数的概念

定义：对于正整数 ,定义 为把 分成 个非空子集的划分个数,称之为第二类Stirling数.

由定义可得：

例1 计算 及 的值.

解:

设一集合 ,将其分为2个非空子集.

设一集合 ,将其分为2个非空子集.

设一集合 ,将其分为1个非空子集.

通过上述计算易知

3 第二类Stirling数的性质

引理1 对任意 第二类Stirling数 满足如下递推关系：

证明：把 分成 个非空子集的划分简称为 的一个 划分.设 是 的一个 划分,

如果 在 中可以作为一个单独的子集 ,那这样我们就可以直接算 的 划分个数,记作 ;或者在元素 在 中不可以作为一个单独的子集的情况下,先将

拿开,那么 中就剩下 个元素,即可以得到一个 的 划分,再把之前拿开的元素

插入任意一个 的 划分可以得到 个不同的 的 划分,易知 的个数为

.

由加法原理得

定理1 满足如下的函数方程：

这里

证明:当 时, ,易知成立.

当 时,对于 的命题也成立,根据递推性质知

由归纳原理易知,该命题对一切正整数 成立,即 满足函数方程.

下面简单由此而得的映射内容:设 为一个正整数,那么从 到 的映射有 个;对 的每个 子集有 个从 到子集的满射.

由定理1知

又因为

故可以变为

例2 第二类Stirling数的基本性质：

(1)

(2)

(3)

证明:

1. 根据上述引理的递推可知

所以由数学归纳法可知结论成立.

1. 根据上述引理的递推可知

得

易知 得

剩余内容已隐藏，请支付后下载全文，论文总字数：5738字