组合数学课件_-_教案讲解.ppt

§5.6 第二类Stirling数定理10-3 §5.6 经典的递推关系 5.6.3 第二类Stirling数 定理 5.10 第二类Stirling数S2(n,k)具有如下性质： S2(n,0)=0 S2(n,1)=1 S2(n,n)=1 S2(n,k)=0 (n＜k或k=0＜n) S2(n,2)=2n-1-1 S2(n,n-1)=C(n,2) 证明： S2(n,m)表示把n个不同的球放入 m个相同的盒子，而且无一盒为空的方式数。如果考虑盒子是编号的。因为m个盒子共有m!种编号方式，于是由乘法法则知共有m!S2(n,m) 种方式把n个不同的球放入m个不同编号的盒子中去，而且没有一个空盒。注：这种方式实际上是第二章§3.1中的例10。 设S表示n个不同的球任意放入m个有编号的盒子里的所有方法的集合，显然|S|=mn 。令pi(i=1,2,…,m)表示盒子i为空这一性质，Ai(i=1,2,…,m)表示S中具有性质pi的元素组成的集合。则 表示没有一个箱子为空的元素集合。 由容斥原理即可得 因此可得 §5.6 第二类Stirling数定理例1 §5.6 经典的递推关系 5.6.3 第二类Stirling数 例 题 例1、把n本不同的书放入m个有编号的箱子中去（n≥m)，使得没有一个箱子为空。共有多少种方法？ 解：这个例子实际上是第三章§3.1中的例10。 通过以上分析可知所求的方式数为 §5.6 第二类Stirling数定理例2 §5.6 经典的递推关系 5.6.3 第二类Stirling数 例 题 例2、设n,m为正整数，n≥m，证明 证明：我们用组合分析法证明。 设有n个不同的球，有 m个盒子，它们的编号为1,2,…,m 。把这n个球放入盒子中去，允许有空盒且不限制放入盒子内的球数，总共有mn种方式。这是由于每个球放到m个盒子中去一共有m种方式。于是n只不同的球放到m个盒子中去，由乘法法则知共有mn种方式。 另一方面，由例1知n个不同的球放入k个不同编号的盒子中去，并且没有一个空盒的方式数为k!S2(n,k) 。而从m个盒子中选取k个盒子的方式数为C(m,k)（显然有m-k个盒子是空的），于是由乘法法则知， n只不同的球放入k个不同盒子中的的方式数为C(m,k) S2(n,k)k! （允许有m-k个空盒）。 当k取1到m ，并把这些数相加所得的和，就是n只不同的球放入 m个不同盒子中去且允许有空盒的方式数。于是有 §5.6 Bell数定义 §5.6 经典的递推关系 5.6.4 Bell数 定义 5.7 若 ，则称Bn为Bell数。其组合含义为n个元素的集合划分为不相交的非空子集的方式数目。显然有B0 =1。 §5.6 Bell数定理 §5.6 经典的递推关系 5.6.4 Bell数 定理 5.11 Bell数Bn满足以下递推关系： 证明：我们用组合分析法证明。 Bn+1为n+1个元素的集合的划分数。在n+1个元素的集合中任意固定一个元素，然后用剩下的n个元素的各种划分来构造n+1个元素的划分。方法如下： 先在n个元素中选取k个元素，这里1≤k≤n，组成一个集合，对它进行划分，其划分数为Bi，而将剩下的n-k个元素和那个固定的元素组成一个子集，形成n+1个元素的一种划分。 这样得到的n +1个元素的划分数为 ，又因为n+1个元素的集合本身也是一个划分，它对应着 。 所以n+1个元素的集合的划分数应该是 §5.6 Catalan数定义 §5.6 经典的递推关系 5.6.4 Catalan数 定义 5.8 一个凸n边形，通过不相交于n边形内部的对角线，把n边形拆分成若干个三角形，不同的拆分方式数目hn，称为Catalan数。 §5.6 Catalan数定理12-1 §5.6 经典的递推关系 5.6.4 Catalan数 定理 5.12 Catalan数满足以下递推关系： (a) hn+1=h2hn+h3hn-1+…+hnh2 证明 ：(a)的证明：如图所示的 n+1边形，以v1vn+1 作为一条边 的三角形的另一个顶点为vk， k=2,3,…,n 。三角形v1vkvn+1 将 凸n+1边形分割成两部分， 一 部分是k边形，另一部分是 n-k+2边形。 根据乘法法则，以v1vkvn+1为一 拆分三角形的拆分数应为 hkhn-k+2, k=2,3,…,n。所得的拆 分各不相同。根据加法法则有 §5.6 Catalan数定理12-2 §5.6 经典的递推关系 5.6.4