排列与组合

第一讲、计数的基本原则

A. 主要知识要点：

1. 有限集、无限集、集合中元素的个数

2. 一一映射、相等原则：设A,B是两个有限集，如果存在由A到B上的一个一一对应映射，则AB.

3. 加法原则 如果完成一件事的全部方法可分成互不相容的K类，其中属于第i(1ik)类的方法有种，则做这件事情的方法共有i1ninki种.

4. 乘法原则 已知做一件事要经过两个步骤，完成第一个步骤的方法有m种，完成第一个步骤之后，完成第二个步骤的方法有n种，则做这件事的方法共有mn种.

B. 典型例题

例1 n名选手参加乒乓球单打淘汰赛，需要打多少场比赛才能产生冠军？

变形：有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军需要进行多少场比赛？

例2：设n为大于1的正整数，求满足条件xyn的有序整数对(x,y)的个数.

1

例3：把4个人分成两组，每组至少1人，求不同的分组方法数.

思考：能否使用包含排斥的问题来解决？

例4.求n元集A{a1,a2,an}的子集的个数.

思考：用乘法原则或者加法原则两种方法进行解答，能否得到多项式的结论.

例5 以N表示万位数字不是5且各位数字互异的5位数的个数，求N.

a2np1a1p2n(n2)例6. 设自然数的质因数分解式为

akpk，求n的不同的正约数的个数.

C. 相关习题：P36 1-5.

第二讲：排列与组合

A.主要知识点：

1.不允许重复的排列问题

例1: （1）从数字{1,2,9}选取数字构成四位数，如果要求每位数字都不相同，问有多少种方法？

（2）从数字{1,2,9}选取数字构成四位数，问有多少种选法？

定义：从n个元素的集合S中有序的选取的r个元素叫做S的一个r排列，不同的排列

2

的总数记作P(n,r).如果rn，则称这个排列S的全排列，简称为S的排列.

定理1：对满足rn的正整数n和r有

n!nr!P(n,r)n(n1)(nr1).

推论1：n元集的全排列的个数为n!.

2.不允许重复的组合问题

定义：从n个元素的集合S中无序的选取的r个元素叫做S的一个r组合，不同的组合的总数记作C(n,r).规定：n0时，我们规定C(n,0)1.

定理2：对满足rn的正整数n和r有

P(n,r)r!C(n,r).

重要概念：含有k种不同元素的多重集S记作{n1a1,n2a2,nkak}

3.多重集的排列问题

定义：从一个多重集S中有序选取的r个元素叫做S的一个r排列.当rn时也叫做S的排列.

例如：S{2a,1b,3c}，acab,abcc是S的4-排列，而abccca是S的排列.

3

r定理3：设多重集S{a1,a2,,ak}则S的r排列数是k.

推论2：设多重集S{n1a1,n2a2,nkak}，且对一切i1,2,k有nir，则S的r排列数是k.

r定理4 设多重集S{n1a1,n2a2,nkak}，且nn1n2n!n1!•n2!••nk!.

nk，则S的排列数等于

4.多重集的组合问题

定义：从一个多重集S中选取的r个元素叫做S的一个r组合.当rn时则S的n-组合只有一个，就是S本身.

例如：S{2a,1b,3c}，S的2-组合有五个，它们是{a,a},{a,b},{a,c},{b,c},{c,c}.

定理5 设多重集S{a1,a2,,ak}则S的r组合数是C(kr1,r).

推论4：设多重集S{n1a1,n2a2,nkak}，且对一切i1,2,k有nir，则S的r组合数是C(kr1,r).

B.典型例题

例1：求由n个相异元a1与a2不相邻的全排列的个数.

4

例2：（1）在5天内安排3次不同的考试，若每天至多安排一次考试，问有多少种排法？

（2）同（1）中，若不限制每天考试的次数，问有多少种排法？

例3：排列26个字母，使得在a和b之间正好有7个字母，问有多少种排法？

例4：（1）10个男孩和5个女孩站成一排.如果没有两个女孩相邻，问有多少种排法？

（2）10个男孩和5个女孩站成一个圆圈，如果没有两个女孩相邻，问有多少种排法？

例5：设由1,2,3,4,5,6组成的各位数字互异的4位偶数共有N个，它们的和记为M，求N和M.

例6：由1,2,3,4,5,6可组成多少个大于35000的5位数？

例7.用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？

例8.求多重集M={5a,3b}的6-排列的个数.

例9：在平面上给定25个点，其中任意三点都不在同一直线上，过两个点可以做一条直线，以三个点为顶点可以做一个三角形，问这样的直线和三角形各有多少？

例10.设An是一个凸n边形，在An的内部任何3条对角线不相交于同一点，求：

（1）An的对角线的条数

5

（2）由An的边和对角线围成的三角形的个数.

例11 求不定方程x1x2xnr的非负整数解的个数.

例12 不定方程x1x2xnr(rn)的正整数解的个数.

例13 把r件相同的物件分给n个人的不同的方法数.

例14 把r件相同的物件分给n(nr)个人，每个人至少分得一件的不同的方法数.

例15 试确定多重集S{1a1,a2,ak}的r组合数.

C. 相关的习题

1.现有100件产品，从其中任意的抽出3件.

（1）共有多少种不同的抽法？

（2）如果100件产品中有2件次品，抽出的产品中至少有1件是次品的抽法有多少种？

（3）如果100件产品中有两件是次品，抽出的产品中恰好有1件是次品的抽法有多少种？

2.有纪念章4枚，纪念册6本，赠给10位同学，每人分得一件，共有多少种不同的送法？

6

3.书架上有9种不同的书，其中4本是红皮的，5本是黑皮的.

（1）9本书的排列有多少种？

（2）若黑皮的书都排在一起，这样的排列有多少种？

（3）若黑皮的书排在一起，红皮的书也排在一起，这样的排列有多少种？

（4）若黑皮的书与红皮的书必须相间，这样的排列又有多少种？

4.（1）15名篮球运动员被分成A、B、C三个组，使得每组有5名运动员，那么有多少种分法？

（2）15名篮球运动员被分成三个组，使得每组有5名运动员，那么有多少种分法？

5.从整数1,2……1000中选取三个数使得它们的和正好被4整除，问有多少种选法？

6.有红球1个，黄球3个，白球3个，把它们排成一条直线，问有多少种排法？

7.从S{0,1,2}中取n个数作成排列，若不允许相邻位置的数相同，问有多少种排法？

8.把字母a,b,c,d,e,f,g,h进行排列，使得a在b的左边，b在c的左边，问这样的排法有多少种？

9.给出多元集{2a1,1b,3c}的所有3-组合和4-组合数.

7

思考：确定多重集S{3a,4b,5c}的10组合数.

完成了思考题，请解答：确定方程x1x2x35(0x12,0x22,1x35)的整数解的个数.

9.P36 6-16 19-32.

第三讲、组合数的基本性质

A.主要知识点

1.组合数的基本性质及二项式定理

nn(nk0)定理1： （1）knk

nn1n1(nk1)（2）kkk1 nnn1(nk1)kk1k（3） nnk1n(nk1)kk1k（4） nnn1(nk0)（5）knkk

8

nmnnk(nmk)定理2：mkkmk

n(xy)xkynk.k0k定理3.（二项式定理）设n是正整数，对一切x和y有

nnn(1x)xk.k0k推论1.设n是正整数，对一切x，有

nnnn推论2.设n是正整数，有01n2nn

nnn推论3.设n是正整数，有012n(1)n0n.

定理4.（多项式定理）设n是正整数，x1,x2,xk是任意k个实数，则

(x1x2xk)nn!n2x1n1x2nk!n1n2nnnn1!n2!xknk

nk1n. 推论1：在的展开式在合并同类项以后不同的项数是

2.组合恒等式

nnnk121.k1k12nnnn2n1n.

9

2nn2kn(n1)2.2.k1k nmnmn3.0r1r1mnmnr0r

mnmn4.0011mnmnmmm

mnmn0011mnmnnnn nn1kk1 nknk1kk

015.kknn16.01B.典型例题

rr1rr1.证明： n1nrr1

2.计算：（1）12n? 1222n2? 1323n3?

2pp3.证明：若是不等于2的素数，则当p被p除时余数是2.

23554.求(12x3x4x)的展开式中x的系数.

10

kn(1)k0 (n2)k5.求证：k1.

n1n1n1(2-1).6.求证：k0k1kn1

nsn1(nm).7.求证：smmm1

n提示：对n进行数学归纳法的证明.

632(2x3x5x)xxx1231238.求中项的系数.

4(xxx)1239.用多项式定理展开.

10342(xxxxx)xxxx5项的系数. 1234512310.确定在的展开式中

n22n211.证明：0212n1n3n11n1nn1.

n1n12.证明：122(1)n11n11nn21.n

1n1提示：先证明：211n1(1).n1nn1再进行数学归纳法.

nC.相关习题

11

习题P36 33-35.

第四讲 鸽巢原理与Ramesy定理

A.主要知识点

1.定理1（鸽巢原理） 把n1个物体放入n个盒子里，则至少有一个盒子含有两个或两个以上的物体.

2.定理2（鸽巢原理的加强形式)设q1,q2,qn都是正整数，若q1q2qnn1放入n个

盒子里，则第一个盒子里至少含有q1个物体，或者第二个盒子里至少含有q2个物体，……，或者第n个盒子里至少含有qn个物体.

3.推论1 若n(r1)1个物体放入n个盒子里，则至少有一个盒子含有r个或者更多的物体

4.推论2 设n个正整数m1,m2,mn满足不等式

1(m1m2,nmn)r1

证明：m1,m2,mn中至少有一个不小于r.

定理3 设G是具有6个顶点的完全图K6,如果我们对它的边任意涂以红色或蓝色，则G中一定包含一个红色的三角形，或者包含一个蓝色的三角形.

12

相关模型：六个人参加宴会一定有三个人是相互认识或者三个人相互不认识的.

定理4 设G是具有10个顶点的完全图K10，如果我们对它的边任意涂以红色或蓝色，则G中一个包含一个红色的三角形或者一个蓝色的完全四边形.

B.典型例题

例1 13个人中至少有两个人是同一个月出生的.

例2 在边长为2的正三角形中任意放5个点，证明至少有两个点之间的距离不大于1.

例3 证明：从任意给出的5个整数中必能选出3个数，它们的和能被3整除。

例4 在n1个小于2n的不相等的正整数中，一定存在两个数是互素的.

例5 设x1,x2,xn是n个正整数，证明其中存在着连续的若干个数，其和是n的倍数.

例6 一个棋手为参加一次锦标赛进行77天的练习，如果他每天至少下一盘棋，而每周至多下12盘棋，而每周至多下12盘棋.证明存在着一个正整数n使得他在这77天里有连续的n天共下了21盘棋.

C.相关习题

1.(1)在边长为1的等边三角形内任意放10个点，证明一定存在两个点，其距离不大于1/3.

13

(2) 确定正整数mn的值，使得在边长为1的等边三角形内任意放mn歌点，其中必有两点的距离不大于1/n.

2.证明在任意的m个连续的整数中存在着一个整数可以被m整除.

3.证明对任意的整数N存在着N的一个倍数，使得它仅由数字0和7组成

4.（1）证明在任意选取的n1个正整数中存在着两个正整数，其差能被n整除.

（2）证明在任意选取的n2个正整数中存在着两个正整数，其差能被2n整除或者其和能被2n整除.

5.某学生有37天的时间准备考试，根据她过去的经验至多需要复习60个小时，但每天至少要复习1小时.证明无论怎样安排都存在连续的若干天，使得她在这些天里恰好复习了13小时.

6.把一个圆盘分成36个相等的扇形，然后把1,2,,36这些数任意填入36个扇形中，证明存在三个连接的扇形，其中的数字之和至少是56.

习题P190 1-14.

14