📄 2_10.htm
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.10 Stirling数 </h1><p> 前面见到的递推关系都是一个参数的。Stirling数问题则不然。它导出的递推关系式是两个参数的。 </p><p> （1）多项式系数 </p><p> n个有区别的球放到两个有区别的盒子里，若要求第1个盒子放k个球，第二个盒子放n-k个球（k=0，1，2，…，n）方案数应是(x<sub>1</sub>+x<sub>2</sub>)<sup>n</sup> 中x<sub>1</sub><sup>k</sup>x<sub>2</sub><sup>n-k</sup>项的系数C(n,k) 依据加法法则有 </p><p> <img border="0" src="2_10.pic/image008.gif" width="221" height="24"></p><p> 可把上面的讨论推广到n个有区别的球放到m个有区别的盒子里，要求m个盒子放的球数分别是n<sub>1</sub>,n<sub>1</sub>,<sup>...</sup>,n<sub>m</sub>(n=n<sub>1</sub>+n<sub>2</sub>+<sup>...</sup>+n<sub>m</sub>)的情况，其不同方案数用 </p><p> <img border="0" src="2_10.pic/image012.gif" width="80" height="51"></p><p>表示。 </p><p> 从n个有区别的球中取出n<sub>1</sub>个放到第1个盒子里去，其选取方案数为</p><p> <img border="0" src="2_10.pic/image016.gif" width="32" height="51">；</p><p>当第1个盒子的n<sub>2</sub>个球选定后，第2个盒子里的n<sub>3</sub>个球则是从n-n<sub>3</sub> 个中选取的，其方案数应为</p><p> <img border="0" src="2_10.pic/image024.gif" width="55" height="51">；</p><p>第3个盒子的n<sub>3</sub>个球则是从n-n<sub>1</sub>-n<sub>2</sub> 中选取，其方案数为 </p><p> <img border="0" src="2_10.pic/image029.gif" width="83" height="51">；</p><p>依此类推，根据乘法法则可得 </p><p> <img border="0" src="2_10.pic/image031.gif" width="252" height="101"></p><p> <img border="0" src="2_10.pic/image033.gif" width="188" height="139"></p><p> n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。对于每一个排列依次取n<sub>1</sub>个放到第1个盒子里，取n<sub>2</sub>个放到第2个盒子里，…，最后n<sub>m</sub>个放到第m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为 </p><p> <img border="0" src="2_10.pic/image038.gif" width="83" height="45"></p><p>结果和（2－10－1）式一致。称</p><p> <img border="0" src="2_10.pic/image040.gif" width="80" height="51"></p><p>为多项式系数。 </p><p> <img border="0" src="2_10.pic/image042.gif" width="261" height="73"></p><p>多项式 (x<sub>1</sub>+x<sub>1</sub>+<sup>...</sup>+x<sub>m</sub>)<sup>n</sup></p><p>的展开式是由（2－10－2）式右端的n项中，每项各取一个元素相乘而得到的。 </p><p> 表达式（2－10－2）中共有n个因子项，令第i个因子项对应于第i个有标志的球，从第i个因子项中取 对应于把第i个有标志的球放到第i个盒子。（2－10－2）式展开的一般项 </p><p> <img border="0" src="2_10.pic/image046.gif" width="229" height="25"></p><p>表示第一个盒子有n<sub>1</sub>个球，第二个盒子有n<sub>2</sub>个球，等等。因此（2－10－2）式中 </p><p> <img border="0" src="2_10.pic/image050.gif" width="80" height="25"></p><p>项的系数应为 </p><p> <img border="0" src="2_10.pic/image052.gif" width="80" height="51"></p><p>即 </p><p> <img border="0" src="2_10.pic/image054.gif" width="283" height="77"></p><p> 定理：(x<sub>1</sub>+x<sub>2</sub>+<sup>...</sup>+x<sub>m</sub>)<sup>n</sup>展开式的项数等于 </p><p> <img border="0" src="2_10.pic/image058.gif" width="77" height="48">，</p><p>而且这些系数之和等于m<sup>n</sup> </p><p> 证明：(x<sub>1</sub>+x<sub>2</sub>+<sup>...</sup>+x<sub>m</sub>)<sup>n</sup>展开式中的 </p><p> <img border="0" src="2_10.pic/image064.gif" width="80" height="25"></p><p>项(n=n<sub>1</sub>+n<sub>2</sub>+<sup>...</sup>+n<sub>m</sub>)和从m个元素x<sub>1</sub>,x<sub>2</sub>,<sup>...</sup>,x<sub>m</sub>中取n个作允许重复的组合一一对应。故得(x<sub>1</sub>+x<sub>2</sub>+<sup>...</sup>+x<sub>m</sub>)<sup>n</sup>展开式的项数等于 </p><p> <img border="0" src="2_10.pic/image072.gif" width="73" height="48">。</p><p>从m个中取n个作允许重复的组合的全体，对于每个球都有m个盒子可供选择，根据乘法法则有 </p><p> <img border="0" src="2_10.pic/image074.gif" width="269" height="51"></p><p> (2)Stirling数 </p><p> 只准备讨论其中的第二类Stirling数,至于第一类的Stirling数只准备给出它的定义和递推关系. </p><p> 定义: 称S(n,0),S(n,1),<sup>...</sup>S(n,n) 为第一类Stirling数 </p><p> <img border="0" src="2_10.pic/image076.gif" width="235" height="75"></p><p>显然有S(n+1,k)=S(n,k-1)-nS(n,k) (2-10-5)</p><p> 定义: n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用S(n,m) 表示,称为第二类Stirling数. </p><p> 例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种: </p><p> <img border="0" src="2_10.pic/image086.gif" width="569" height="76"></p><p>其中r表红球,y表黄球,b表蓝球,w表白球, </p><p> <img border="0" src="2_10.pic/image088.gif" width="93" height="21"></p><p> 定理: 第二类StirlingS(n,k) 有下列性质: </p><p> (a) S(n,0)=0, (b) S(n,1)=1,</p><p> (c) S(n,2)=2<sup>n-1</sup>-1, (d) S(n,n-1)=C(n,2),</p><p> (e) S(n,n)=1.</p><p> 证明:公式(a),(b),(e)是显然的,只证(c),(d). </p><p> (c)设有n个不相同的球b<sub>1</sub>,b<sub>2</sub>,<sup>...</sup>,b<sub>n</sub>从中取出球b<sub>1</sub>,其余的n-1个球,每个都有与b<sub>1</sub>同盒,或不与b<sub>1</sub>同盒两种选择.但必须排除一种情况,即全体与b<sub>1</sub>同盒,因这时另一盒将是空盒.故实际上只有2<sup>n-1</sup>-1 种方案, 即S(n,2)=2<sup>n-1</sup>-1</p><p> (d)n个球放到n-1个盒子里,不允许有一空盒,故必有一盒有两个球,从n个有区别的球中取2个共有C(n,2)种组合方案. </p><p> 定理: 第二类Stirling数满足下面的递推关系, </p><p> <img border="0" src="2_10.pic/image106.gif" width="319" height="45"></p><p> 证明: 设有n个有区别的球b<sub>1</sub>,b<sub>2</sub>,<sup>...</sup>,b<sub>n</sub>从中取一个球设为b<sub>1</sub>.把n个球放到m个盒子无一空盒的方案的全体可分为两类。</p><p> （a）b<sub>1</sub>独占一盒，其方案数显然为S(n-1,m-1)</p><p> （b）b<sub>1</sub>不独占一盒，这相当于先将剩下的n-1个球放到m个盒子，不允许空盒，共有S(n-1,m)种不同方案，然后将b<sub>1</sub>球放进其中一盒，从乘法法则得b<sub>1</sub>不独占一盒的方案数应为mS(n-1,m)根据加法法则有 S(n,m)=S(n-1,m-1)+mS(n-1,m)</p><p> 上面证明递推公式（2－10－6）的过程，也就是给出构造所有方案的办法。例如今将红、黄、蓝、白、绿五个球放到无区别的两个盒子里。 </p><p> <img border="0" src="2_10.pic/image124.gif" width="260" height="21"></p><p>故共有15种不同的方案。 </p><p> 先把绿球取走，余下的四个球放到两个 盒子的方案已见前面的例子。和前面一样用 r，y，b，w分别表示红，黄，蓝，白球，绿 球用g表示，故得表（2－10－1） </p><p>表 2-10-1 </p><p> <img border="0" src="2_10.pic/image126.gif" width="533" height="151"></p><p> n个球放到m个盒子里，依球和盒子是否有区别？是否允许空盒？共有2<sup>3</sup>=8 种状态。其方案计数分别列于下表。 </p><ul> <li> n个球有区别，m个盒子有区别，有空盒时方案计数为m<sup>n</sup></li> <li> n个球有区别，m个盒子有区别，无空盒时方案计数为m!S(n,m)</li> <li> n个球有区别，m个盒子无区别，有空盒时方案计数为 </li></ul><p> <img border="0" src="2_10.pic/image134.gif" width="191" height="91"></p><ul> <li> n个球有区别，m个盒子无区别，无空盒时方案计数为S(n,n)</li> <li> n个球无区别，m个盒子有区别，有空盒时方案计数为C(n+m-1,n)</li> <li> n个球无区别，m个盒子有区别，无空盒时方案计数为</li></ul><p> <img border="0" src="2_10.pic/image140.gif" width="153" height="69"></p><ul> <li> n个球无区别，m个盒子无区别，有空盒时方案计数为 的 项系数。</li> </ul> <p> <img border="0" src="2_10.pic/image142.gif" width="204" height="44"></p><ul> <li> n个球无区别，m个盒子无区别，无空盒时方案计数为</li></ul><p> <img border="0" src="2_10.pic/image146.gif" width="204" height="47"></p><p>的x<sup>n</sup>项系数。 </p><p> 利用S(n,m)=S(n-1,m-1)+mS(n-1,m),S(n,1)=S(n,n)=1 ，还可以如Pascal三角形一样得到表2-10-3。表 2-10-3见书119页。</p> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -