例1 用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串？
定理2.3.2 多重集合
M?{k1?a1,k2?a2,?,kn?an}
(k?k???kn)!的全排列数为12。
k1!k2!?kn!
例2 求2.2节例7中9人小组的进站方案。
解：设9个人分别为a1,a2,?,a9，分界符为“?”，则集合
M?{a1,a2,?,a9,5??}的每个全排列对应着9人的一种进站方案，总的方案种数为
14!?726485760。
1!???1!?5!
例3 下图中，从(0，0)点沿水平和垂直道路可走到(m,n)点，问有多少种走法？
(m,n) ?m?n?解： 每条路径对应着多重集合M?{m?x,n?y}的一个全排列，即一共有??种
m??不同的走法。
例4 将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？
(0,0) 2.3.2 多重集合的组合
多重集合M的r组合是指从M中无序地选取r个元素。
定理2.3.3 多重集合
M?{??a1,??a2,?,??an} 的r组合数为Ckr?r?1。
例5 从M?{1,2,?,n}中能够取出多少个长为r的递增序列a1,a2,?,ar，使得
ai?1?ai?s?1(s?0;i?1,2,?,r?1)。
定理2.3.4 多重集合 M?{??a1,??a2,?,??ak}
?1要求a1,a2,?,ak}至少出现一次的r组合数为Crk?1。
定义2.3.1 设集合X?{x1,x2,?,xm}是一个全序集，x1?x2???xm，那么由 X中的n个字母构成的字符串xi,xi,?,xi，只要xi?xi???xi，就称其为X
12n12n上长度为n的增字。
定理2.3.5 设集合X?{x1,x2,?,xm}是一个全序集，则X上长度为n的增字共有
nCm?n?1?1个。
第四节 二项式系数
2.4.1 二项式定理
定理2.4.1(二项式定理) 设n为一正整数，则对任意的x和y，有
122n?2n?1n?1(x?y)n?yn?Cnxyn?1?Cnxy???Cnxy?xn
rrn?r??Cnxy。 r?0n
定理2.4.2(牛顿二项式定理) 对一切实数?和x(x?1)，有
???r??(??1)?(??r?1)r(1?x)????x??xr!r?0?r?r?0
2.4.2 二项式系数的基本性质
n?
?n??n?（1）对称关系?????。
?r??n?r?（2）递推关系 ?n??n?1??n?1?????????(n?r?1)。 rrr?1??????（3）单峰性 （略）
2.4.3 组合恒等式
?n??n??n?等式1：???????????2n。
?0??1??n??n??n??n??n??n??n?等式2：?????????????????????。
?0??2??4??1??3??5??n??n??n?等式3：1????2??????n???n?2n?1。
?1??2??n??0??1??n??n?1?等式4：?????????????。
kkkk?1????????2nn???2n?等式5：??????。
k?0?k??n??m??n??m?n?等式6：????????。
i?0?i??r?i??m?r?
2.4.3 多项式定理
定理2.4.3(多项式定理) 设n为正整数，则
n??n1n2nt(x1?x2???xt)n???xx?x?12t
?n1n2?nt?mn??n!其中? ??nn?nn!n!?n!t??1212t称为多项式系数；而其中的求和号是对所有满足
n1?n2???nt?n
的非负整数序列n1,n2,?,nt求和。
3例1 展开(x1?x2?x3?x4?x5)7，则x12x3x4x5的系数为
7!?420。
2!0!1!3!1!
3例2 展开(2x1?3x2?5x3)6，则x12x3x4x5的系数为 6!?23?(?3)?52??36000。 3!1!2!
注： 在多项式定理中，其右端的求和号中所包含的项数就是方程
n1?n2???nt?n
n的非负整数解的数目，即Cn?t?1项。
第五节 集合的分划与第二类Stirling数
定义2.5.1 设A1,A2,?,Ak是A的k个子集，若它们满足：
(1)Ai??(1?i?k)；
(2)Ai?Aj??(1?i?j?k)； (3)A?A1?A2???Ak。
则称{A1,A2,?,Ak}是A的一个k分划，并记为
A?A1?A2???Ak
???称Ai(1?i?k)为A的上述k分划的一个块。
定义2.5.2 一个n元集合的全部k分划的个数叫做第二类Stirling数，记作S(n,k)。
定理2.5.1 第二类Stirling数S(n,k)满足递推关系 S(n?1,k)?S(n,k?1)?kS(n,k)(1?k?n)。
证明：S(n?1,k)是集合A?{a1,a2,...,an,an?1}的k分划的个数，这些k分划可以分为两类：
第(1)类：{an?1}是A的k 分划中的一个块。这时，只需对集合A?{an?1}进行m-1分划，再加上{an?1}这一块，就构成了A的k分划。这类分划有S(n,k?1)个。
第(2)类：{an?1}不是A的k分划中单独的一块。此时，先构造A?{an?1}的k分划，共有S(n,k)种方法。然后，对于A?{an?1}的每个k分划，将an?1加到该k分划的k个块中的某一块，从而构成A的k分划。因此，由乘法原理，集合A的此类k分划共有kS(n,k)个。
综上所述知原命题成立。
定理2.5.2 第二类Stirling数S(n,k)满足下列性质： （1）S(n,2)?2n?1?1；
2（2）S(n,n?1)?Cn； （3）S(n,1)?1;S(n,n)?1;S(n,k)?0(k?n)。
定理2.5.3 第二类Stirling数S(n,k)满足递推关系 S(n?1,k)?S(n,k?1)?kS(n,k)(1?k?n)。 注：令
?x?n?x(x?1)(x?2)?(x?n?1)，
若
?x?n??S1(n,k)xk，
k?0n则称S1(n,k)为第一类Stirling数。换句话说，S1(n,k)就是多项式?x?n中的xk系数。显然，当n?k时，S1(n,k)?0。
例： ?x?4?x(x?1)(x?2)(x?3)?x4?6x3?11x2?6x。由定义，有
S1(4,0)?0,S1(4,1)??6,S1(4,2)?11,S1(4,3)??6,S1(4,4)?1。
定理： 第一类Stirling数满足如下递推关系： ?S1(n?1,k)?S1(n,k?1)?nS1(n,k)(n?0,k?0) ??S1(0,0)?1,S1(n,0)?0(n?0)
注： 第二类Stirling数也可以由下式定义：
x??S(n,k)[x]k。
nk?0n
第六节 正整数的分拆
定义2.6.1 正整数n的一个k分拆是把n表示成k个正整数的和
n?n1?n2???nk(k?1)
的一种表示法，其中
ni?0(1?i?k)
ni称为该分拆的分部量。如果表达式是无序的，即对诸ni任意换位后的表示法都只视为一种表示法，这样的分拆称为无序分拆，或简称为分拆。反之，若表达式是有