【重、难点解析】 (一)排列 1.无重复元素的排列（线排列） 从n个元素的集合S中选出r个元素的排列，称为排列。其个数为： Pu)=nn-1n-2y小n-r+）=-r 从n个元素的集合S中选出n个元素的排列，称为全排列。其个数为： p(n,n)=n 2.无重复元素的圆排列（环排列） 从n个元素的集合S中选出r个元素排列成圆环，称为圆排列。其个数为： P(n,r)_ r(n-r)! 公式解释n个元素的排列有P(n,r）个，而其中的任何一个排列a,a2,,a,的顺序 移动：4，…，a,aa,a4,…,a,4；…a,a,,a共r个。因此n个元素的r-圆排列数 为： =- r 当n-r时，n个元素的集合S的全圆排列数为： P(n,n)=(n-1)! 3.重复排列 设S={m,丸，乃b2,,nb},则S所有元素的不同的m重复排列数为： (+n2+…n川 n,ln2…n 设S={ob,ob2,…,obn},则S的r可重复全排列数为m。 (二)组合 1.无重复元素的组合数 从n个元素的集合S中选出r个元素组成一组，称为八组合。其个数为： C:-P(n.r)_(n-1X(n-2)(nr+)= rl(n-r)! 2.n个元素的集合S的一可重复组合数 从n个元素的集合S中选出r个元素的可重复组合数，记作F(nr) F(n,r）=C1=C
【 】 （一）排 列 1．无重复元素的排列（线排列） 从 n 个元素的集合 S 中选出 r 个元素的排列，称为 r-排列。其个数为： ( )! ! ( , ) ( 1)( 2) ( 1) n r n P n r n n n n r − = − − − + = 从 n 个元素的集合 S 中选出 n 个元素的排列，称为全排列。其个数为： p(n,n) = n! 2．无重复元素的圆排列（环排列） 从 n 个元素的集合 S 中选出 r 个元素排列成圆环，称为 r-圆排列。其个数为： ( )! ( , ) ! r n r n r P n r − = 公式解释 n 个元素的 r-排列有 P(n,r) 个，而其中的任何一个排列 a a ar , , , 1 2 的顺序 移动： 2 1 3 4 1 2 1 1 , , , ; , , , , ; ; , , , a ar a a a a a ar a ar− 共 r 个。因此 n 个元素的 r-圆排列数 为： ( )! ( , ) ! r n r n r P n r − = 当 n=r 时，n 个元素的集合 S 的全圆排列数为： ( 1)! ( , ) = n − n P n n 3．重复排列 设 { · , · , , · } S = n1 b1 n2 b2 nk bk ，则 S 所有元素的不同的 n-重复排列数为： ! ! ! ( )! 1 2 1 2 k k n n n n n n + + 设 { · , · , , · } S = b1 b2 bn ，则 S 的 r-可重复全排列数为 n r。 (二)组 合 1．无重复元素的组合数 从 n 个元素的集合 S 中选出 r 个元素组成一组，称为 r-组合。其个数为： !( )! ! ! ( 1)( 2) ( 1) ! ( , ) r n r n r n n n n r r P n r C k n − = − − − + = = 2．n 个元素的集合 S 的 r-可重复组合数 从 n 个元素的集合 S 中选出 r 个元素的 r-可重复组合数，记作 F（n,r）: 1 1 1 ( , ) − = + − = + − n n r r F n r Cn r C
公式解释设有n个元素S={亿，b2,,b},与自然数1,2，…m,建立一一对应关系。 所考虑的任何组合可以看作是一个，个数的数组(B,6)。由于是数组，不妨 认为b,按大小顺序排列，相同的b,(可以重复)连续地排在一起，如按b1≤b2≤…≤b,≤n 排列。令d=b+i-1(=l,2,,),于是 d=h,d42=b2+l…,dn=b,+r-1 由于b,最大可取n,那么d,最大可取n+r-1。有 d,d2,…,d,(d<d2<…≤dn<n+r-) 从而将问题转化为求集合(1,2，…，n+r1)的组合问题，易见，有一种{b,血，；的取 法，就有一种d.d ,d的取法 对应 这样，允许重复地从n个不同元素中取r个元素的组合数和不允许重复地从+元素 中取♪个元素的组合数是相同的。故有公式 fn,r）=C=C 3.组合恒等式 (1)C-C,+C (2)C8+C+C:++Cg=2C=2” (3C:-C+C-(-C:-('C-0 'cic:-0 ()2c=n2 (6)Cg+C+Cm2+…+Cm=C (Scic-ci. (三)筛法原理 筛法原理也称为容斥原理，又称包含排列原理。 筛法原理是用以解决集合的元素计数个数、概率中一般和事件的概率计算公式。 在计数问题中，常采用间接计算一个集合的元素个数，比直接计算容易些。如，某单 位集会，共有187人到会。由于某种需要，想知道男米宾的人数。但是，女米宾人数易计算 出来。二者之差即为男来宾数。 在集合计数中：
公式解释 设有 n 个元素 { , , , } S = b1 b2 bn ，与自然数 1,2,…,n，建立一一对应关系。 所考虑的任何 r-组合可以看作是一个 r 个数的数组（b1, b2,…, bn）。由于是数组，不妨 认为 bi 按大小顺序排列，相同的 bi（可以重复）连续地排在一起，如按 b1≤b2≤…≤br≤n 排列。令 di= bi+i-1(i=1,2,…,r)，于是 d1 = b1 ,d2 = b2 +1, ,dr = br + r −1 由于 i b 最大可取 n，那么 i d 最大可取 n + r −1 。有 , , , ( 1) d1 d2 dr d1 d2 dr n + r − 从而将问题转化为求集合（1,2,…，n+r-1）的 r-组合问题，易见，有一种{b1, b2,…, br}的取 法，就有一种{d1, d2,…, dr}的取法。它们一一对应。 这样，允许重复地从 n 个不同元素中取 r 个元素的组合数和不允许重复地从 n+r-1 元素 中取 r 个元素的组合数是相同的。故有公式 1 1 1 ( , ) − = + − = + − n n r r f n r Cn r C 3．组合恒等式 （1） 1 1 1 − = − + − r n r n r Cn C C （2） = + + + + = = n k k n n n Cn Cn Cn Cn C 0 0 1 2 2 （3） = − + − − = − = n k k n n k n n Cn Cn Cn C C 0 0 1 2 ( 1) ( 1) 0 （4） = − = n k r k n r k k ( 1) C C 0 （5） = − = n k k n kCn n 1 1 2 （6） 1 1 2 1 + + + + + + + + = + + n n m n n m n n n n n Cn C C C C （7） = + − = k i k m n k i n i CmC C 0 （三）筛法原理 筛法原理也称为容斥原理，又称包含排列原理。 筛法原理是用以解决集合的元素计数个数、概率中一般和事件的概率计算公式。 在计数问题中，常采用间接计算一个集合的元素个数，比直接计算容易些。如，某单 位集会，共有 187 人到会。由于某种需要，想知道男来宾的人数。但是，女来宾人数易计算 出来。二者之差即为男来宾数。 在集合计数中：
1AU42H4+|A1-|A∩41 1AnA日S1-|A1-1421+1A∩42 |A∩A2∩A曰S1-1A|-142|-|A|+|A∩A21 +1A∩4l+|4∩41-|A∩4∩4 推而广之： |4004HS1-∑A1+∑lAn4,l- ∑14∩4，∩41+…+(-1) An4n-n41++ (-1）"14∩A2∩…Am1 设S是有N个元素的集合，41是S的具有性质P(1)的子集，其元素个数A记作M: 42是S的具有性质P(2)的子集，其元素个数4记作：…A∩A,是S的同时具有性 质P()和P(n)的子集，其元素个数A,∩A1记作N6:…A∩A。∩∩A,是S 的同时具有性质P(i)P(i2)…P(i)的子集，其元素个数A∩A∩…∩A,I记作N4: A∩A∩…门An是S的不具有P(i)(l,2…,m)任何性质的子集，其元素个数 |A∩A,∩∩A记作N(0)。于是上面式改写成： N()-N+ (-ly∑Nhw+…-)Na 这正是本章第3节的公式(43-1)。 (四)递推公式与分部 1.初等几何问题 平面上n条一般直线（任何两直线不平行，任何三条直线不共点），将平面分成几个部 分（区域）日 用P,表示n条直线所分平面的部分数（区域数），有： 当=0时，没有直线，平面是一个整体，即 P=1 当1时，一条直线，将平面分成2个部分，即 D=2=B。+1=P+m 当=2时，2条直线，将平面分成4个部分，即
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1 3 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 A A A A A A A A A A S A A A A A A A S A A A A A A A A A A + + − = − − − + = − − + = + − 推而广之： = − + − = i j i j m i | A A Am | | S | | Ai | | A A | 1 2 + + − i j k r Ai Aj Ak | | ( 1) ( 1) | | | | 1 2 1 2 1 2 m m i i i i i i A A A A A A r r − + + ① 设 S 是有 N 个元素的集合，A1 是 S 的具有性质 P（1）的子集，其元素个数| A1|记作 N1； A2 是 S 的具有性质 P（2）的子集，其元素个数|A2|记作 N2；… 1 2 Ai Ai 是 S 的同时具有性 质 P（i1）和 P（i2）的子集，其元素个数| 1 2 Ai Ai |记作 1 2 Ni ,i ；… r Ai Ai Ai 1 2 是 S 的同时具有性质 P（i1）P（i2）…P（ir）的子集，其元素个数| r Ai Ai Ai 1 2 |记作 r Ni ,i , ,i 1 2 ； A1 A2 Am是S 的不具有 P（i）（i=1,2,…,m）任何性质的子集，其元素个数 | A1 A2 Am |记作 N（0）。于是上面①式改写成： m m i i i i i i r i i i i i i i j i i m i i N N N N N N N k k , , , 1,2, , , , , 1 ( 1) ( 1) (0) 1 2 1 2 1 2 3 1 2 3 1 2 1 2 − + + − = − + − + + = 这正是本章第 3 节的公式（4-3-1）。 （四）递推公式与分部 1．初等几何问题 平面上 n 条一般直线（任何两直线不平行，任何三条直线不共点），将平面分成几个部 分（区域）？ 用 Pn 表示 n 条直线所分平面的部分数（区域数），有： 当 n=0 时，没有直线，平面是一个整体，即 1; P0 = 当 n=1 时，一条直线，将平面分成 2 个部分，即 2 1 ; P1 = = P0 + = P0 + n 当 n=2 时，2 条直线，将平面分成 4 个部分，即
B=4=R+2=R+m 当严3时，3条直线，将平面分成7个部分，即 E=7=B+3=P+m如图(47) XX 1=0 =1 1=2 图47直线分割平面示意图 依此类推，一般地，有公式n=P+n 且Pn=Pn+n= Pn-2+(n-1)+n= B+2+3++(n-2)+(n-1)+n= 1+1+2+3+…+m-2)+m-)+n=m++1 2.递推公式与斐波那契(Fibonacci)数列 例有 一个人把一一对（瞻雄各一）的大鱼子放在自家的院子里饲养，他粗知首一年后 能生出多少对兔子 ,假定这对大兔子每月可生雌雄各一的一对小兔子，而新生的一对小兔了 经过一个月可以长成大免子，以后也是每月产雌雄各一的一对小兔子。问：一年后（也就是 到第13个月开始)能生出多少对兔子？ 解由题设知，第一个月有一对兔子，第二个月开始时有两对兔子（大、小兔子各 对)，第三个月开始，新出生的小兔子刚长成大兔子还不能产仔，只有原来的一对大兔子产 仔一对，共有2+1=3对兔子，它是第一、第二两个月免子对数的总和。 第四个月开始时，除第三个月出生的一对兔子不产仔外，其余的两对兔子都能产仔， 共产小兔子2对，与第二个月兔子的对数相同，因此共有2+3=5对，它等于第二、第三两 个月免子对数的总和。 一般地，可这样考虑：我们用)表示第n个月初兔子的对数。因为第n个月开始时 除第m】个月新生的兔子不能产仔外，其余的兔子，即在第：2个月时己有的兔子都能产仔， 而第m-2个月共有兔子数为m-2)对 第n个月新生的小兔子共有-2) 又因为第n个月的兔子是由两部分组成，一部分是在第m】个月时已有的兔子，共1) 对：另一部分是第n个月新生的小兔子，有-2)对。因此，第n个月共有： n=n-1)+m-2) 公式①给出了连续多年兔子数之间的关系，我们称公式①为递推公式。 我们已经知道：1)=122，当n≥3时，利用公式①可以计算出m)的值如下 八3=1+2= 43+2 f5=5+3=8 6=8+5=13 7)=13+8=21 8)=21+13=34 f9)=34+21=55 10=55+34=89
4 2 ; P2 = = P1 + = P1 + n 当 n=3 时,3 条直线，将平面分成 7 个部分，即 7 3 ; P3 = = P2 + = P2 + n 如图（4-7） n=0 n=1 n=2 n=3 图 4-7 直线分割平面示意图 依此类推，一般地，有公式 Pn = Pn−1 + n 且 Pn = Pn−1 + n = 1 2 ( 1) 1 1 2 3 ( 2) ( 1) 2 3 ( 2) ( 1) ( 1) 1 2 + + + + + + + − + − + = + + + + − + − + = − + − + = n n n n n P n n n Pn n n 2．递推公式与斐波那契（Fibonacci）数列 例 有一个人把一对（雌雄各一）的大兔子放在自家的院子里饲养，他想知道一年后 能生出多少对兔子，假定这对大兔子每月可生雌雄各一的一对小兔子，而新生的一对小兔子 经过一个月可以长成大兔子，以后也是每月产雌雄各一的一对小兔子。问：一年后（也就是 到第 13 个月开始）能生出多少对兔子？ 解 由题设知，第一个月有一对兔子，第二个月开始时有两对兔子（大、小兔子各一 对），第三个月开始，新出生的小兔子刚长成大兔子还不能产仔，只有原来的一对大兔子产 仔一对，共有 2+1=3 对兔子，它是第一、第二两个月兔子对数的总和。 第四个月开始时，除第三个月出生的一对兔子不产仔外，其余的两对兔子都能产仔， 共产小兔子 2 对，与第二个月兔子的对数相同，因此共有 2+3=5 对，它等于第二、第三两 个月兔子对数的总和。 一般地，可这样考虑：我们用 f(n)表示第 n 个月初兔子的对数。因为第 n 个月开始时， 除第 n-1 个月新生的兔子不能产仔外，其余的兔子，即在第 n-2 个月时已有的兔子都能产仔， 而第 n-2 个月共有兔子数为 f(n-2)对，故第 n 个月新生的小兔子共有 f(n-2)。 又因为第 n 个月的兔子是由两部分组成，一部分是在第 n-1 个月时已有的兔子，共 f(n-1) 对；另一部分是第 n 个月新生的小兔子，有 f(n-2)对。因此，第 n 个月共有： f(n)= f(n-1)+ f(n-2) ① 公式①给出了连续多年兔子数之间的关系，我们称公式①为递推公式。 我们已经知道：f(1)=1 ,f(2)=2,当 n≥3 时，利用公式①可以计算出 f(n)的值如下： f(3)=1+2=3 f(4)=3+2=5 f(5)=5+3=8 f(6)=8+5=13 f(7)=13+8=21 f(8)=21+13=34 f(9)=34+21=55 f(10)=55+34=89
f11)=89+55=14412)=144+89=233 13)-=233+144-377 解得 一年后《即第13个月) 有兔子377对 若规定0)=1,1)=1，由递推公式①可得到数列 1.1.2.3.5.8.13.2134.55.89.144233.377.… 数学界把这个数列叫做斐波那契数列，以纪念最先得到这个数列的数学家[斐波那契 (Leonardo Fibonacci),(约1170-1250)，是意大利数学家]。由于这个数列在数学、物理、 化学领域经常出现，又具有很奇特的性质，所以美国数学会每三个就出版 一本专门对这种数 列进行研究的季刊，称为《斐波那契季刊》。 递推公式①的另一解释为：设n-样本(a1,42,,an)集合，若a,只能取0或1，求不允 许连续出现两个0的样本个数，用m)表示。记O)1, 当=1时，即1-样本(a)a,取0或1，有2个样本：(0)，(1)片故1=2： 当n=2时，即2样本(a,a2)。有样本(11)，(01)，(10)，故2)-3， 当=3时，即3-样本(a,a2a)。有样本(111)，(101)，(110)，(011)，(010)。即， a=1时，样本个数为1)23: a1=0时，am只能取1，样本个数为n-2)=1=2 故3)=5=2+1片m-1片m-2) 当=4时，即4样本(a1a2asa)。有样本 1111).(1011),(1010),(1101). (10),(011),(0110),(0101) 4)=83+2Fm-1片m-2) 以此类推，同样能得到递推公式 n)=m-1)+fn-2) 3.扰周排列 设S={1,2…,n,(am,®，…，a)和(b,b加…，)是S的两个排列，对于一切，12,…n 有a,≠b,则称(b1,b2,,4)是(a,a,,)的一个扰乱排列，或称错位排列、移位排 列。即每个数码都不在原来位置上的排列。 如(4321)和(3412)都是(1234)的扰乱排列。而(1324)和(1432)都不是(1234) 和扰乱排列，因为不是每个数码都不在原位置。 用D(n)表示n个元素的扰乱排列的个数 设A是S的所有排列的集合： A=川 令A,为第i个元素定位在1的S的所有排列.A|表示第i个元素定位在i的的排列数， i1,2,…n Dm)A-I心A1 因为元素1定位在1的所有排列数为(m-1)【,即|A=(m1)(=12,…,)
f(11)=89+55=144 f(12)=144+89=233 f(13)=233+144=377 解得：一年后（即第 13 个月）有兔子 377 对。 若规定 f(0)=1，f(1) =1，由递推公式①可得到数列 1,1,2,3,5,8,13,21,34,55,89,144,233,377,… 数学界把这个数列叫做斐波那契数列，以纪念最先得到这个数列的数学家[斐波那契 （Leonardo Fibonacci）,(约 1170~1250)，是意大利数学家]。由于这个数列在数学、物理、 化学领域经常出现，又具有很奇特的性质，所以美国数学会每三个就出版一本专门对这种数 列进行研究的季刊，称为《斐波那契季刊》。 递推公式①的另一解释为：设 n-样本 ( , , , ) a1 a2 an 集合，若 i a 只能取 0 或 1，求不允 许连续出现两个 0 的样本个数，用 f(n)表示。记 f(0)=1， 当 n=1 时，即 1-样本 1 1 (a ) a 取 0 或 1，有 2 个样本：（0），（1）；故 f(1)=2； 当 n=2 时，即 2-样本 ( ) a1a2 。有样本（11），（01），（10），故 f(2)=3; 当 n=3 时，即 3-样本（ a1a2a3 ）。有样本（111），（101），（110），（011），（010）。即， a1=1 时，样本个数为 f(n-1)=f(2)=3； a1=0 时，a2 只能取 1，样本个数为 f(n-2)=f(1)=2 故 f(3)=5=f(2)+f(1)=f(n-1)+f(n-2) 当 n=4 时，即 4-样本（a1a2a3a4）。有样本 (1111)，（1011），（1010），（1101）， （1110），（0111），（0110），（0101）。 故 f(4)=8=f(3)+f(2)=f(n-1)+f(n-2) 以此类推，同样能得到递推公式 f(n)=f(n-1)+f(n-2) 3．扰乱排列 设 S={1,2,…，n}，（a1,a2,…，an）和（b1,b2,…,bn）是 S 的两个排列，对于一切 i，i=1,2,…,n, 有 ai bi ，则称（b1,b2,…,bn）是（a1,a2,…，an）的一个扰乱排列，或称错位排列、移位排 列。即每个数码都不在原来位置上的排列。 如（4321）和（3412）都是（1234）的扰乱排列。而（1324）和（1432）都不是（1234） 和扰乱排列，因为不是每个数码都不在原位置。 用 D（n）表示 n 个元素的扰乱排列的个数。 设 A 是 S 的所有排列的集合： | A |= n! 令 Ai 为第 i 个元素定位在 i 的 S 的所有排列。 | | Ai 表示第 i 个元素定位在 i 的的排列数， i=1,2,…,n。 ( ) | | | | 1 i n i D n A A = = − 因为元素 i 定位在 i 的所有排列数为（n-1）!，即 | | Ai =（n-1）!(i=1,2,…，n)
S的两个元素的定位排列数为A,∩A,上(n-2训 S的k个元素的定位排列数为门A卡(n-k! 由筛法原理： 1A4卡Cg141-C14n4,1++(-)-C1A4 C(n-1)1-C2(n-2)+…+(-1)-C0 所以D(m)=l- 面到++少r l川 容易证明： Dn)=(n-1[D(n-1)+Dn-2l 个排列(a,电…，，如果有r个a排列，则称为S的r定位排列， 如S的一个排列(1234)，则(1243)和(1432)是S的一个2定位排列，而(1342) 不是S的2定位排列，只是1定位排列。 S是r定位排列数用N(r)表示。 因为有r定位排列，剩余m-r是扰乱排列，有D(mr).而n个元素选r个的方式有C:个。 于是n个元素的集合S的r定位排列数为： N(r)=CD(n-r)= 0-分 …+(-) (n-)) 5.从n个数码的集合中取出k个数码，不出现两个连续数码的个数 设S是n个数码{1,2，，川的集合，从S中取出k个数码，不出现有2个连续数码的个 数是 f(n.k)=C 当m1视为连续数时，从S中取出k个数码，不出现有2个连续数码的个数为： 8(n.k)=n-kC 6.数山的计算 Un=per(J-I-C)∑aua…a 其中J是元素全为1的n阶方阵，I是n阶恒等矩阵（单位矩阵），C是上次对角线为1， 即a:=a==a.=l,其余元素为0的n阶方阵：∑a4.0表示矩阵C 的所有不同行不同列的n个元素乘积之和。其中1不能取1,2：2不能取2,3：a不能取
S 的两个元素的定位排列数为 | A A |= (n − 2)! i j S 的 k 个元素的定位排列数为 | | ( )! 1 A n k i k i = − = 由筛法原理： = − + + − = = − = | | | | | | ( 1) | | 1 1 2 1 1 i n i n n n i n i n i j n i A C A C A A C A ( 1)! ( 2)! ( 1) 0! 1 2 1 n n n Cn n Cn n C − − − − ++ − 所以 = − + − + − + − = ! ! ( 1) 4! ! 3! ! 2! ! 1! ! ( ) ! n n n n n n D n n n ] ! 1 ( 1) 4! 1 3! 1 2! 1 1! 1 ![1 n n n − + − + −+ − 容易证明： D(n) = (n −1)[D(n −1) + D(n − 2)] 4．定位排列 设 S 是一个排列（a1,a2,…，an），如果有 r 个 ai=i 排列，则称为 S 的 r 定位排列。 如 S 的一个排列（1234），则（1243）和（1432）是 S 的一个 2 定位排列，而（1342） 不是 S 的 2 定位排列，只是 1 定位排列。 S 是 r 定位排列数用 N（r）表示。 因为有 r 定位排列，剩余 n-r 是扰乱排列，有 D（n-r）.而 n 个元素选 r 个的方式有 r Cn 个。 于是 n 个元素的集合 S 的 r 定位排列数为： ) ( )! 1 ( 1) 4! 1 3! 1 2! 1 1! 1 (1 ! ! ( ) ( ) r n r n N r C D n r n r r n − − + − + − + − = − = − 5．从 n 个数码的集合中取出 k 个数码，不出现两个连续数码的个数 设 S 是 n 个数码{1,2,…,n}的集合，从 S 中取出 k 个数码，不出现有 2 个连续数码的个 数是 k Cn k f n k 1 ( , ) = − + 当 n,1 视为连续数时，从 S 中取出 k 个数码，不出现有 2 个连续数码的个数为： k Cn k n k n g n k − − ( , ) = 6．数 Un的计算 nin Un = per J − I −C a i a i a 1 1 2 2 ( ) 其中 J 是元素全为 1 的 n 阶方阵，I 是 n 阶恒等矩阵（单位矩阵），C 是上次对角线为 1， 即 12 = 23 = = ( −1) = 1 n n a a a ，其余元素为 0 的 n 阶方阵： nin a i a i a 1 1 2 2 表示矩阵 J-I-C 的所有不同行不同列的 n 个元素乘积之和。其中 i1 不能取 1,2； i2 不能取 2,3；…in 不能取
1。 显然a,a2,…an的值要么是1，要么是0. 或用下公式计算： U.=nl-Ci (n-1)!+8(2n.2X(n-2)- g(2n,32n-3+…+(-1)g(2n,n0 其中g(n,k)= 7.分部 分部就是将正整数表成若干个正整数之和。 有序分部可重复一分出的正整数可重复出现 分部 不可重复一分出的正整数不能重复 可重复一分出的正整数可重复出现 无序部分 不可重复一分出的正整数不能重复 现以正整数4的分部为例，说明各个概念，见下表。 表414的分部表 有序分部 无序分部 备注 不允许重复4=4,4=1+3,4=3+14=4,4=3+1 允许重复 44 4-4 在 一个分部 4=1+3,4=3+1 4=1+3 中数字重复 4=2+2,4=2+1+1 4=2+2,4=2+1+1 出现 4=1+2+1,4=1+1+2 4=1+1+1+1 4=1+1+1+1 设n是正整数，则不定方程 n=x1+x2+…+x(x,>0,i=12…,k) 的正整数解就称为n的分部。如表41中，正整数4的有序不重复分部有3个：无序不重复 分部有2个：有序重复分部有8个，无序重复分部有5个。 我们若重讨论允许重复的分部。 (1)n的可重复的k个有序正整数解的个数 不定方程n=X+x2+…+x,(x,>0,i=1,2,…,k)的k个可重复的有序正整数解的个 数，记作P(m,有 P.(n)=CA 举例验证。如M=7: 1,即7表成1个正整数之和，显然x1=7.则 P(7)=1=C8=C
n,1。 显然 nin a i a i a 1 1 2 2 的值要么是 1，要么是 0。 或用下公式计算： = !− ( −1)!+ (2 ,2)( − 2)!− 1 Un n C2n n g n n g(2n,3)(2n 3)! ( 1) g(2n,n)·0! n − ++ − 其中 k Cn k n k n g n k − − ( , ) = （见教材本章定理 4.7）。 7．分 部 分部就是将正整数表成若干个正整数之和。 不可重复 分出的正整数不能重复 可重复 分出的正整数可重复出现 无序部分 不可重复 分出的正整数不能重复 可重复 分出的正整数可重复出现 有序分部 分部 — — — — 现以正整数 4 的分部为例，说明各个概念，见下表。 表 4-1 4 的分部表 有 序 分 部 无 序 分 部 备 注 不允许重复 4=4，4=1+3，4=3+1 4=4，4=3+1 允许重复 4=4 4=1+3，4=3+1 4=2+2，4=2+1+1 4=1+2+1，4=1+1+2 4=1+1+1+1 4=4 4=1+3 4=2+2，4=2+1+1 4=1+1+1+1 在一个分部 中数字重复 出现 设 n 是正整数，则不定方程 ( 0, 1,2, , ) 1 2 n x x x x i k = + ++ k i = 的正整数解就称为 n 的分部。如表 4-1 中，正整数 4 的有序不重复分部有 3 个；无序不重复 分部有 2 个；有序重复分部有 8 个，无序重复分部有 5 个。 我们着重讨论允许重复的分部。 （1）n 的可重复的 k 个有序正整数解的个数 不定方程 ( 0, 1,2, , ) 1 2 n x x x x i k = + ++ k i = 的k个可重复的有序正整数解的个 数，记作 Pk(n),有： 1 1 ( ) − = − k Pk n Cn 举例验证。如 n=7: k=1,即 7 表成 1 个正整数之和，显然 x1=7.则 1 1 0 1 1 6 (7) − = = = − k P C Cn
k=2,即7表成2个正整数之和：x+2=7,有2+5,5+2,4+3,3+4,6+1,1+6共6 个，则 P(7=6=C6=C k-3,即7表成3个正整数之和：x+x2+x=7,有1+1+5,1+5+1,5+1+1,2+1+4， 2+4+1,1+2+4,1+4+2,4+1+2,4+2+1,3+3+1,3+1+3,1+3+3,2+2+3,2+3+2,3+2+2 共15个，则 P(⑦=15=C6=C k4,即7表成4个正整数之和：x+为2+x3+x4=7,有：1+1+1+4,1+1+4+1,1+4+1+1， 4+1+1+1,1+1+2+3,1+1+3+2,1+2+3+1,1+3+2+1,2+3+1+1,3+2+1+1,1+2+1+3,1+3+1+2, 2+1+3+1,3+1+2+1,2+1+1+3,3+1+1+2,1+2+2+2,2+1+2+2,2+2+1+2,2+2+2+1 共20个。则 P(7)=20=C=C 5,即7表成5个正整数之和：+x2++x4+x=7,有：1+1+1+1+3,1+1+1+3+1， 1+1+3+1+1,1+3+1+1+1,3+1+1+1+1,1+1+2+1+2,1+2+1+1+2,2+1+1+1+2,2+1+1+2+1, 2+1+2+1+1,2+2+1+1+1,1+2+2+1+1,1+1+2+2+1,1+1+1+2+2,2+1+1+1+2, 共15个，则 P,(7)=15=Cg=C k=6,即7表成6个正整数之和：x1+2+x3+x4+x3+x6=7,有：1+1+1+1+1+2， 1+1+1+1+2+1,1+1+1+2+1+1,1+1+2+1+1+1,1+2+1+1+1+1,2+1+1+1+1 共6个，则 P,(7)=6=Cg=C =7,即7表成7个正整数之和：x+x2+x+x4+x+x6+x,-7,只有 1+1+1+1+1+1+1 共1个。 P,(⑦)=1=Cg=C (2)n的可重复的k个无序正整数解的个数 不定方程n=x1+x2++x(,>0,1=1,2,…,k的k个可重复的无序正整数解的个 数，仍记作P(m,有 P(n)=∑P(n-k)
k=2,即 7 表成 2 个正整数之和： x1 + x2 = 7 ，有 2+5，5+2，4+3，3+4，6+1，1+6 共 6 个，则 1 1 1 2 6 6 (7) − = = = − k P C Cn k=3,即 7 表成 3 个正整数之和： x1 + x2 + x3 = 7 ，有 1+1+5，1+5+1，5+1+1，2+1+4， 2+4+1，1+2+4，1+4+2，4+1+2，4+2+1，3+3+1，3+1+3，1+3+3，2+2+3，2+3+2，3+2+2 共 15 个，则 1 1 2 3 15 6 (7) − = = = − k P C Cn k=4,即 7 表成 4 个正整数之和： x1 + x2 + x3 + x4 = 7 ，有：1+1+1+4，1+1+4+1，1+4+1+1， 4+1+1+1，1+1+2+3，1+1+3+2，1+2+3+1，1+3+2+1，2+3+1+1，3+2+1+1，1+2+1+3，1+3+1+2， 2+1+3+1，3+1+2+1，2+1+1+3，3+1+1+2，1+2+2+2，2+1+2+2，2+2+1+2，2+2+2+1 共 20 个。则 1 1 3 4 20 6 (7) − = = = − k P C Cn k=5,即 7 表成 5 个正整数之和： x1 + x2 + x3 + x4 + x5 = 7 ，有：1+1+1+1+3，1+1+1+3+1， 1+1+3+1+1，1+3+1+1+1，3+1+1+1+1，1+1+2+1+2，1+2+1+1+2，2+1+1+1+2，2+1+1+2+1， 2+1+2+1+1，2+2+1+1+1，1+2+2+1+1，1+1+2+2+1，1+1+1+2+2，2+1+1+1+2， 共 15 个，则 1 1 4 5 15 6 (7) − = = = − k P C Cn k=6,即 7 表成 6 个正整数之和： x1 + x2 + x3 + x4 + x5 + x6 = 7 ，有：1+1+1+1+1+2， 1+1+1+1+2+1, 1+1+1+2+1+1, 1+1+2+1+1+1, 1+2+1+1+1+1, 2+1+1+1+1 共 6 个，则 1 1 5 6 6 6 (7) − = = = − k P C Cn k=7, 即 7 表 成 7 个 正 整 数 之 和 ： x1 + x2 + x3 + x4 + x5 + x6 + x7 = 7 ，只有 1+1+1+1+1+1+1 共 1 个。 1 1 5 7 1 6 (7) − = = = − k P C Cn （2）n 的可重复的 k 个无序正整数解的个数 不定方程 n x x x x i k k = 1 + 2 ++ k ( i 0, =1,2, , )的 个可重复的无序正整数解的个 数，仍记作 P (n) k ,有 = = − k i k i P n P n k 1 ( ) ( )
易知，P(n)=1,当k>n时，P(n)=0. 举例验证。如 当1时，=1，即1=1，所以P(1)=1 当=2时，=1，即2=2，所以P1(2)=1: k-2,即2=1+1，所以P2(2)=1。 当=3时，仁1，即3=3，所以P1(3)=P1(2)=1: 当F4时，k1,即4=4，所以P:(4)=P(3)=1 k-2,即4=2+2或1+3，所以P2(4)=P1(2)+P2(2)=+1=2 k=3.即4=3+1，所以P:(4)=P,(1)+P,(1)+P3(1)=10+0+1 当5时，即55，所以P《 k-2,即5=1+4或2+3，所以 P2(5)=P1(3)+P3(3)=1+1=2 =3,即5=2+2+1,3+1+1，所以 P3(5)=P1(2)+P2(2)=1+1=2 4,即5=1+1+1+2，所以 P4(5)=P1(1)+P(1)=1+0= k=5,即5=1+1+1+1+1，所以P5(5)=1 8.用母函数计算组合问题 母函数又叫生成函数。它是解决计数问颗的一个有力工具，我们先看两个例子。 例1袋内有4个红球，3个白球，2个黑球。从袋中任取4个球，问有多少种不同的取 法。 解考虑如下表达式： fx)=(1+x+x2+x3+x41+x+x2+x3)1+x+x2)= (1+3x+16x2+9x3+11x+） 在第1个括号中的指数k可认为代表k个红球，第2个括号中达的指数k可认为代 表k个白球，第3个括号中的x的指数k可认为代表k个黑球。 如果用x。表示第个括号里的“，那么 X=x 就是一种（取法）方案，它表示取1个红球，2个白球，1个黑球的一种取法：而 x28,=x 也是一种方案，它表示取红球4个，白球、黑球都不取的一种取法 每次取4个球，所有不同的取法个数就是x)的展开式中x的系数1。 例2若有1g2g,3g4g的砝码各一枚，问能称出哪几种重量？有几种可能的方案？ (1+x1+x21+x31+x)=
易知， Pn (n) =1,当k n时，P k (n) = 0 。 举例验证。如： 当 n=1 时，k=1,即 1=1，所以 P1（1）=1。 当 n=2 时，k=1,即 2=2，所以 P1（2）=1； k=2,即 2=1+1，所以 P2（2）=1。 当 n=3 时，k=1,即 3=3，所以 P1（3）= P1（2）=1； k=2,即 3=1+2，所以 P2（3）= P1（1）+ P2（1）=1； k=3,即 3=1+1+1，所以 P3（3）=1。 当 n=4 时，k=1,即 4=4，所以 P1（4）= P1（3）=1 k=2,即 4=2+2 或 1+3，所以 P2（4）= P1（2）+ P2（2）=1+1=2 k=3,即 4=3+1，所以 P3（4）= P1（1）+ P2（1）+ P3（1）=1+0+0+1 k=4,即 4=1+1+1+1，所以 P4（4）=1。 当 n=5 时，k=1,即 5=5，所以 P1（5）= P1（4）=1 k=2,即 5=1+4 或 2+3，所以 P2（5）= P1（3）+ P2（3）=1+1=2 k=3,即 5=2+2+1，3+1+1，所以 P3（5）= P1（2）+ P2（2）=1+1=2 k=4,即 5=1+1+1+2，所以 P4（5）= P1（1）+ P2（1）=1+0=1 k=5,即 5=1+1+1+1+1,所以 P5（5）=1 8．用母函数计算组合问题 母函数又叫生成函数。它是解决计数问题的一个有力工具，我们先看两个例子。 例 1 袋内有 4 个红球，3 个白球，2 个黑球。从袋中任取 4 个球，问有多少种不同的取 法。 解 考虑如下表达式： ( ) = (1+ + + + )(1+ + + )(1+ + ) = 2 3 4 2 3 2 f x x x x x x x x x x (1 3 16 9 11 ) + x + x 2 + x 3 + x 4 + 在第 1 个括号中 x k 的指数 k 可认为代表 k 个红球，第 2 个括号中 x k 的指数 k 可认为代 表 k 个白球，第 3 个括号中的 x k 的指数 k 可认为代表 k 个黑球。 如果用 k k i x 表示第i个括号里的x ( ) ，那么 4 (3) 2 (1) (2) x x x = x 就是一种（取法）方案，它表示取 1 个红球，2 个白球，1 个黑球的一种取法；而 0 4 (3) 0 (2) 4 (1) x x x = x 也是一种方案，它表示取红球 4 个，白球、黑球都不取的一种取法。 每次取 4 个球，所有不同的取法个数就是 f(x)的展开式中 x 的系数 11。 例 2 若有 1g,2g,3g,4g 的砝码各一枚，问能称出哪几种重量？有几种可能的方案？ (1+ )(1+ )(1+ )(1+ ) = 2 3 4 x x x x
1+x+x2+2x3+2x+2x5+2x6+2x2+2x8+x9+x0 这里第1个括号中x的指数1可认为代表1g的砝码1枚，第2个括号中x的指数2可认为 代表2g的砝码1枚，余类推。 在展开式中：如2的指数5表示可称5g重物，系数2则表示称5g重物有2种方案（因 为2x5=x2x3+xx,即用2g与3g砝码各一枚，可称出5g的重量：用1g和4g的砝码各 枚，也能称出5g的重量)。从展开式知道，用1g2g,3g和4g的砝码各一枚，能称出1g 和10g的重量。展开式中各项的系数，便是方案数。 下面考虑多重集。设 A={ka1,k2a2,…,knan} 它表示集合A有k个a,k个a2,…,k个a· 设想有标号分别为1,2，…n的盒子在第i个盒子里放有k,个球a,(亿=L,2,…,m)。 所谓多重集A的一个组合，就是指由A中的可重复的r个元素构成的一个组合，那 么多重集A的一个如下的5组合： a aaaa 则对应于从第1个盒子里取出2个球，第2个盒子里取出2个球，第3个盒子里取出1个球 的一种取法：同样，多重集A的一个7组合： 对应于从第1个盒子里取3个球，第3个盒子里取2个球，第4个盒子里取2个球的一种取 法。反之，从第1个盒子里取1个球，第2个盒子里取3个球，第4个盒子里取1个球，则 对应于多重集A的一个5-组合。 a ada.a, 所以，多重集A的组合数就等于从n个盒子里一共取出r个球的不同取法数。如果x代表 球，x代表从第1个盒子里取出个球，x中代表从第2个盒子里取出力个球，…并且满足 条件 +2+…+n=r 6,≤k,j=1,2…,m 那么项 xx…x=x 就对应多重集A={化a1,k242,…,k4n}的一个r组合，而 1+x+…+x41+x++x)(1+x+…+x) 的展开式中项x的系数就是多重集A的户组合数，它恰好等于从n个盒子里每次取出r个 球的所有不同取法数
2 3 4 5 6 7 8 9 10 1+ x + x + 2x + 2x + 2x + 2x + 2x + 2x + x + x 这里第 1 个括号中 x 的指数 1 可认为代表 1g 的砝码 1 枚，第 2 个括号中 x 的指数 2 可认为 代表 2g 的砝码 1 枚，余类推。 在展开式中：如 2x 5 的指数 5 表示可称 5g 重物，系数 2 则表示称 5g 重物有 2 种方案（因 为 5 2 3 4 2x = x x + xx ，即用 2g 与 3g 砝码各一枚，可称出 5g 的重量；用 1g 和 4g 的砝码各 一枚，也能称出 5g 的重量）。从展开式知道，用 1g,2g,3g 和 4g 的砝码各一枚，能称出 1g 和 10g 的重量。展开式中各项的系数，便是方案数。 下面考虑多重集。设 { , , , } 1 1 2 2 n an A = k a k a k 它表示集合 A 有 n an k1个a1 ,k2个a2 , ,k 个 。 设想有标号分别为 1,2,…,n 的盒子在第 i 个盒子里放有 i k 个球 a (i 1,2, ,n) i = 。 所谓多重集 A 的一个 r-组合，就是指由 A 中的可重复的 r 个元素构成的一个组合，那 么多重集 A 的一个如下的 5-组合： a1a1a2a2a3 则对应于从第 1 个盒子里取出 2 个球，第 2 个盒子里取出 2 个球，第 3 个盒子里取出 1 个球 的一种取法；同样，多重集 A 的一个 7-组合： a1a1a1a3a3a4a4 对应于从第 1 个盒子里取 3 个球，第 3 个盒子里取 2 个球，第 4 个盒子里取 2 个球的一种取 法。反之，从第 1 个盒子里取 1 个球，第 2 个盒子里取 3 个球，第 4 个盒子里取 1 个球，则 对应于多重集 A 的一个 5-组合。 a1a2a2a2a4 所以，多重集 A 的 r-组合数就等于从 n 个盒子里一共取出 r 个球的不同取法数。如果 x 代表 球， 1 i x 代表从第 1 个盒子里取出 i1 个球， 2 i x 代表从第 2 个盒子里取出 i2 个球，…并且满足 条件 i i i r 1 + 2 ++ n = (i k , j 1,2, ,n) j j = 那么项 i i i r x x x x n = 1 2 就对应多重集 { , , , } 1 1 2 2 n an A = k a k a k 的一个 r-组合，而 (1 )(1 ) (1 ) 1 2 n k k k + x ++ x + x ++ x + x ++ x 的展开式中项 x r的系数就是多重集 A 的 r-组合数，它恰好等于从 n 个盒子里每次取出 r 个 球的所有不同取法数