【重、难点解析】 (一)排列 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)