数学竞赛讲义：排列与组合.pdf

《数学竞赛讲义：排列与组合.pdf》由会员分享，可在线阅读，更多相关《数学竞赛讲义：排列与组合.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学竞赛讲义：排列与组合【赛点直击】一、两个基本原理加法原理设 A 为完成一件事情的所有方法的集合，它可以划分为n 个互不相交的非空子集A1，A2，,，An，|Ai|=mi(i=1,2,n)，那么完成这件事情的总方法数为：N=|A|=m1+m2+,+mn；使用加法原理的关键在于对所计数的对象进行完全分类乘法原理设 A 为完成一件事情的所有方法的集合，且完成这件事情需要几个步骤，实现第i(i=1,2,n)个步骤的方法的集合为Ai，|Ai|=mi,那么完成这件事情的总方法数为N=|A|=m1 m2,mn；使用乘法原理的关键在于对所计数的对象进行完全分步二、相异元素的排列与组合（1）从 n 个不同元

2、素中，任取m 个不同元素的排列数是!(1)(1)()!mnnAnnnmnm；（2）从 n 个不同元素中，任取m 个不同元素的组合数是!()!mnnCnm；三、圆排列定义从 n 元集中任取r 个不同元素，仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n 个不同元素的r-圆排列，其排列数记为rnH由定义，不难求得：rnH与组合数rnC和排列数rnA的关系为：rArCHrnrnrn)!1(事实上设已将某r 个不同元素在圆周上排好，并从某个元素开始将它们依次记为rAAA,21，现在保持这个顺序不变，让1A去任意选择圆周上的r 个位置之一，有r 种不同的选择，这r 种选择所对应的排列形式不同

3、实则相同由于r 个元素的全排列数为!r，故 r 个元素的圆排列数为)!1(r，故 n个元素的圆排列数为)!1(rCrn四、重复排列定义从 n 元集中允许重复地任取r 个元素排成一列，称为n 个不同元素的r-可重排列利用乘法原理易证明，n 个不同元素的r-可重排列数为rn，这类问题一般可直接用乘法原理求解五、不全相异元素的全排列定义设 n 个元素可分为k 组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为in),.,2,1(ki，nnnnk.21，则这n 个元素的全排列称为不全相异元素的全排列n 个元素的不全相异元素的全排列个数为!.!21knnnn，证明如下：先把每组中

4、的元素看作是不相同的，则n 个不同元素的全排列数为!n，然后分别将每个组的元素还其本来面目每个组的元素是相同的，则在这!n 个全排列中，每个排列都重复出现了12!.!knnn次，所以不全相异元素的全排列数为!.!21knnnn六、多组组合定义将 n 个不同的元素分成k 组的组合称为n 个不同元素的k-组合对于一个n 个不同元素的k-组合，若第i 组有in个元素，（ki,.,2,1），则不难证明不同的分组方法数为!.!21,.,21knnnnnnnnCk事实上，我们把分组的过程安排成相继的k 个步骤：第一步，从 n 个不同元素中选1n个，有1nnC种方法；第二步，从1nn个元素中选2n个有21n

5、nnC种方法，,，第k步，从121.knnnn个元素选kn个元素，有kknnnnnC).(121种方法，再由乘法原理得证七、重复组合定义从 n 个不同的元素中任取r 个允许重复出现的组合称为n 个不同元素的r可重组合不难证明，n 个不同元素的r可重组合的个数为rrnC1事 实 上，设（raaa,.,21）是 取 自 1,2,n 中 的 任 一r-可 重 复 组 合，并 设raaa.21，令)1(1riiabii，从而11ab，122ab，233ab，,，1rabrr，显然下面两组数是一对一的：raaa.21，11.211321rnraaaar设Ariraaanaaaa.,.,2,1|),.,(

6、2121，Brirbbbrnbbbb.,1,.,2,1|),.,(2121，则由A、B 之间存在一一对应，可知rrnCBA1|，得证在上述证明中，设r-可重复组合raaa,.,21中含有1x个1，2x个 2，,，nx个 n，则rxxxn.21，且显然有（raaa,.,21）与（nxxx,.,21）一一对应，因此我们立即可得：定理 1 不定方程rxxxn.21的非负整数解的个数为rrnC1定理 2 不定方程rxxxn.21的正整数解的个数为11nrC证 明：令1iixy，其 中1ix，（nxxx,.,21）是 已 知 方 程 的 正 整 数 解，则nryyyn.21（*），由定理1 知，方程（*

7、）有1111)(nrnrrnrrnnCCC个正整数解【赛题解析】例 1在由n2个小方格组成的正方形中，有多少个由整数个小方格组成的大小或位置不同的正方形？解：由整数个小方格组成的大小位置不同的正方形可分成n 类，第k 类为 kk 的正方形，共有2)1(kn个(k=1,2,n)，于是由加法原理得所求正方形的总个数为)12)(1(61)1(12nnnknNnk说明：此题将问题进行分类，直接用加法及乘法原理进行求解，两个原理是解决排列组合问题最基本的工具例 2设整数a,b,c 为三角形三边，a+b=nN,1?c?n-1，求这样的整边三角形的个数解：不妨设b?a，有 1?a?2n，这样的整边三角形可分

8、为两类第一类：c 为最大边，令ia，则inb，n-i?c?n-1，这样的三角形有iinn1)()1(个；第二类：c 不为最大边，则baccb,，故incinab2，故112incin，这样的三角形有11)12()1(iinin由加法原理，使a+b=n 的整边三角形的个数为21)1()(niiinf22n例 3有多少个能被3 整除而又含有数字6 的五位数？解：易知，在由10000 99999 这 90000 个五位数中，共有30000 个可被 3 整除，下面先求其中不含数字 6 的有多少个这件事情可分步来完成：在最高位，不能为0 和 6，因此有8 种可能的情况，在千、百、十位上，不能为 6，各有

9、 9 种可能的情况，在个位上，不能为6，且应使整个五位数能被3 整除，因此所出现的数应与前4 位数字之和被3 除的余数有关：当该余数为2 时，个位上可为1，4，7 中的一个；当该余数为 1 时，个位上可为2，5，8 中的一个；当该余数为0 时，个位上可为0，3，9 中的一个，总之，不论前4 位数如何，个位数字都有3 种可能情况所以这类五位数的个数为899 93=17496，因此，含数字6 而又可被3 整除的五位数的个数为30000-17496=12504 种可能例 4从 1，2，3，4，,，49 中取出六个不同的数字，其中至少有两个是相邻的取法种数是多少？解：设126,a aa 是取自 1，2

10、，3，4，,，49 中的六个不同的数，不妨设126aaa，显然12345612345aaaaaa，且123456,1,2,3,4,5a aaaaa互不相同的充要条件是：126,a aa 中不含相邻的数作六元数组126(,)a aa对应于123456(,1,2,3,4,5)a aaaaa，则在取自1 至 49 之间的六个不同且没有相邻的数构成的六元组集合与所有取自1至 44 之间的六个不同的数构成的六元组集合之间建立了一一对应，因此这两个集合中六元组的个数都为644C，而 1 至 49 之间的六个不同的数构成的六元组的个数为649C，于是，其中有相邻数的六元组的个数为664944CC说明：本题通

11、过对应的方法将数相邻的问题转化为元素互异的问题，从而得到求解，对应的方法是解决排列组合问题的一种常用方法例 5如图 ABCDEF 为六边形，一只青蛙开始在顶点A处，它每次可随意跳到相邻两个顶点之一（1）若在 5次内跳到D点，则停止跳动；若5 次内不能跳到D点，跳完 5 次也停止跳动问这只青蛙从开始到停止，可能出现的不同跳法有几种？（2）若青蛙共跳12 次，最终跳回到A点的不同跳法有几种？解：（1）由条件，青蛙的跳法只可能出现两种情况：跳 3 次到达 D点，有 2 种跳法跳 5 次停止（前3 次不到 D点），注意到前3 次的32种跳法中，有2种到达 D点，故前 3 次有3226种跳法，而后2 次

12、有22种跳法，因此有26224种跳法由、可知，共有2+24=26 种不同的跳法（2）设青蛙每逆时针跳一步记为+1，每顺时针跳一步记为-1，共跳 12 次，将所有这些数相加，若其和为 6 的倍数，则青蛙跳回A 处，若其和不为6 的倍数，则青蛙不可能跳回原处，若其和为0，则必为 6 个+1 和 6 个-1 相加，共有612C种可能；若其和为6，则必为 9 个+1 和 3 个-1 相加，共312C种；若其和为-6，则必为 3 个+1 和 9 个-1 相加，共312C种；若其和为12，则有 1 种可能，若其和为-12，也A B C D E F S5S4S3S2S1有一种可能，因此满足要求的不同跳法总数

13、为63121222CC种例 6将一个四棱锥S-ABCD 的每个顶点染上一种颜色，并使同一条棱的两端点异色，如果只有5 种颜色可供使用，那么不同的染色方法的总数是多少？解法一：由题设，四棱锥S-ABCD 的顶点 S、A、B 所染的颜色互不相同，它们共35A种染色方法当 S、A、B 已染好时，不妨设其颜色分别为1、2、3，若 C 染颜色 2，则 D 可染颜色3、4、5 之一，有 3 种染法；若C 染颜色 4，则 D 可染颜色3或 5，有 2 种染法；若C 染颜色 5，则 D 可染颜色3 或 4，也有 2 种染法，由此可见，当S、A、B 已染好时，C 与 D 还有 7 种染法，从而总的染色方法数为

14、735A=420 种解法二：满足题设条件的染色至少要用三种颜色（1）若恰用三种颜色，可先从5 种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A、B、C、D 四点，此时只能A 与 C、B 与 D 分别同色，故有60122415CCC种方法；（2）若恰用四种颜色染色，可以先从5 种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染 A 与 B，由于 A 与 B 颜色可以交换，故有24A种染法，再从余下的两种颜色中任选一种染D 或 C，而 D 与 C 中另一个只需染与其相对顶点同色即可，故有24012122415CCAC种方法；（3）若恰用5 种颜色染色，易知有12055A种染法综上所

15、知，满足题意的总染色方法数为60+240+120=420 种类题：（2003 年高考江苏第15 题）某城市在中心广场建造一个花囿，花囿分为6 个部分（如图），现要栽种 4 种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种（以数字作答）解法一：1、2、3 两两相邻，颜色应互不相同，故有34A种不同种法；1、2、3种好后，用树图方法不难得到4、5、6 共有 5 种种法，由乘法原理得共有34A 5=120 种种法解法二：先种1，有 4 种颜色可选取，2、3、4、5、6 形成一个圆环，要求用3 种颜色涂上，且相邻的颜色不同即可转化为如下问题：将一个圆分成5 个扇形，将

16、三种颜色涂入其中，相邻的扇形涂不同的颜色先涂1S，有三种涂法，再涂2S，有两种涂法，再涂3、4 各有两种涂法，再涂5，如果只要求它与4 颜色不同，则仍有两种涂法，这样共有3222 2=48 种涂法，但这48 种涂法中有两类：一类 5 与 1 颜色不同，这种涂法符合题意，其数设为5a一类 5 与 1颜色相同，这种涂法不合题意，如果把 5 与 1 合并看成一个扇形，这类涂法就相当于把圆分成4 个扇形，按题设要求，其数为4a，即5a+4a=48，同理，34aa=24，而6333Aa，5a=30，故最后的结果为：304=120 种此问题可一般化为：把一个圆分成)2(nn个扇形，依次记为,21nSSS每

17、个扇形都可用红、白、蓝三种不同颜色之任一种涂色，且三种颜色均至少用一次，要求相邻的扇形颜色互不相同，问有多少种涂色法？略解：同上可得：,6,5,4,2311naannn，63a若没有条件“颜色均至少用一次”，结果为,6,5,4,2311naannn，62a更一般的情形是：把一个圆分成)2(nn个扇形，依次记为,21nSSS每个扇形都可用r 种不同颜色之任一种涂色，要求相邻的扇形颜色互不相同，问有多少种涂色法？有11(1),4,5,6,nnnaarrn，可得nnnrra)1()1)(1(说明：当我们用集合划分的方法对问题进行分类计数时，有时不可能一次性获得成功，这就需要通过建立递推关系来求解，我

18、们把这种计数方法称为递推方法例 7设集合 A=1,2,3,366，如果 A 的一个二元子集B=a,b满足 17|a+b，则称 B 具有性质P（1）求 A 的具有性质P 的所有二元子集的个数；（2）求 A 的两两不相交且具有性质P的所有二元子集的个数解：（1）a+b0(mod17)，即 ak(mod17)且 b17-k(mod17)，k=0,1,2,16，将 1,2,3,366 按模 17 可分为 17 类0,1,16；因 366=1721+9，故|1|=|2|=,=|9|=22，|10|=|11|=,=|16|=|0|=21，欲 17|a+b，当且仅当a,b0或 ak，b17-k，当 a,b0

19、时，具有性质P 的二元子集的个数为221C个；当 ak，b17-k，k=1,2,7 时，具有性质P的二元子集有1211227CC个；当 a8，b9 时，具有性质P 的二元子集有121121CC个；所以 A 的具有性质P 的二元子集总个数为39287121121121122221CCCCC个说明：如果把子集换成数对（a,b），则共有23928 个（2）为使二元子集两两不交，可作如下搭配：a,b 0时，共有10 个子集；ak，b17-k，k=1,2,7，有 21 个子集；当 a8，b9 时，有 22 个子集故 A 的具有性质P 的两两不交的二元子集共有10+721=179 个例 8 8 个女孩和2

20、5 个男孩围成一圈，任何两个女孩之间至少站两个男孩，问共有多少种不同的排列方法（只要把圈旋转一下就重合的排法认为是相同的）解：以 1 个女孩和2 个男孩为一组，且使女孩恰好站在两个男孩中间，余下的9 个男孩和这8 个组被看成是17 个元素，显然这17 个元素任意的圆排列数为1616A种再次，分在8 个组内的16 个男孩在16 个位置上的排列是1616A，所以总的排列方法数为：16161616925AAC说明：此题为圆排列问题例 9试求从集合nA,.,2,1到集合mB,.,2,1的映射的个数解：由映射的定义知，每一个到B 的映射对应着m个不同元素的n-可重排列，故从A 到 B 的映射的个数为nm

21、例 10一段楼梯共有12 级台阶，某人上楼时，有时一步迈一台阶，有时一步迈两台阶，问此人共有多少种上楼的方法？解：现将“一步迈两级台阶”这一动作记为a，因为楼梯共有12 级台阶，故动作a 至多只能做6次；再记“一步迈一级台阶”的动作为b，则上楼的整个过程由k 个 a 及 12-2k 个 b 组成，这里k 可取0，1，2，3，4，5，6，对于某个k，其全排列数为：)!212(!212(kkkk)!212(!)!12(kkk，因此，上楼的方法共有：60)!212(!)!12(kkkk=233 种解法 2：以 k=4 为例，即 4 个两级，4 个一级，相当于共8 步，其中有四步为两级，即相当于从8步

22、中选 4 步跨两级，其余跨一级，故结果应为48C；一般地上楼的整个过程由k 个 a 及 12-2k 个 b 组成，相当于共跨k+(12-2k)=12-k 步，其中有 k 步为a，故结果为kkC12,这里 k 可取 0,1,2,3,4,5,6，故最终结果为6012kkkC解法 3：设走 n 次台阶的方法总数为na，对每种走法可划分为两类第一类：第一步走 1 级，有1na种走法；第二类：第一步走2 级，有2na种走法，故21nnnaaa，且2,121aa，故易得23312a因Fibonacci 数列nF满足2,1321FFF，故1nnFa，由上面的一些方法还可知：201nkkknnCF若将所跨的每

23、一级台阶，此人均用红、白两种颜色做上记号，则标有不同颜色的路线共有202132niiniinnC种，其递推关系式为5,2,22121aaaaannn例 11把 n 个不同的球，分别装入m 个盒子中，使其中1m个盒子中每个都有1p个球，2m个盒子中 每 个 都 有2p个 球，,，km个 盒子 中 每 个都 有kp个 球，这 里，kkkmpmpmpnmmmm.,.221121，求下列情况下，各有多少种不同放法：（1）盒子均不相同；（2）装有相同数目的球的盒子相同解：（1）这 是 一 个 将n个 不 同 元 素 分 为m组 的 多 组 组 合，故 不 同 的 放 法 数 有kmkmmpppnf)!.

24、()!()!(!2121；（2）因为相同数目的球的盒子相同（不加区别），故所求放法数为!.!21kmmmf例 12电视台在n 天内共播出r 次商业广告，问若每天至少播p 次广告（rnp），就每天播出广告的次数而言，共有几种播出方法？解：设 第i天 播 出 广 告ix次，由 题 设 知：rxxxn.21，),.,2,1(nipxi，令pxyii，则0.21npryyyn，故问题转化为求上述不定方程的非负整数解的个数，从而知广告播放的方法数为nprnnprC1)(巩 固 练 习1n 名同学(n?3)站成一圈，其中A、B 两人不能相邻的站法有多少种？解：n 名同学站成一圈有(n-1)!种站法，其中使

25、A、B 相邻的站法有2(n-2)!种，从而A、B不相邻的站法为(n-1)!-2(n-2)!=(n-3)(n-2)!种站法2设集合A、B 的并集为一个n 元集，AB（1）若（A，B）与（B，A）视为不同的对，则这样的A、B 共有多少个？（2）若（A，B）与（B，A）视为相同的对，则这样的A、B 共有多少个？解：（1）设集合A 中有 k 个元素，则集合B 中必含有A 中没有的n-k 个元素，再加上A 的 k 个元素中取0 个、1 个、,k 个，故共有kknC2个，故总数为nkkknC02=n3个，除去A 与 B 相同（均为全集）的1 个，共n3-1 个；（2）由题意，（A，B）与（B，A）一一对应

26、，故结果为)13(21n个3在一个正六边形的六个区域栽种观赏植物，如图，要求同一块中种同一植物，相邻的两块种不同的植物，现有4 种不同的植物可供选择，则有多少种不同的栽种方案解：考虑 A、C、E 种同一种植物，此时共有 433 3=108 种；考虑A、C、E种两种植物，此时共有343322=432 种方法；考虑A、C、E种三种 植 物，此 时 共 有34C 2 2 2=192种 方 法；故 总 计 有108+432+192=732 种方案4如图，矩形ABCD 的边在网格线上，并且AB 是 AD 的 k 倍（k 为正整数），考虑沿网格的边从 A 到 C 所有可能的最短路径证明：在这些路径中，含A

27、B1的条数是含AD1的条数的k 倍解：含 AB1的最短路径，除AB1外，还应含横 向 的m-1 节，纵向的n 节，因此共有1nm nC条，同理，含AD1的最短路径有1mm nC条，而11!(1)!(1)!nm nmm nCm nmkCn mn，因此命题得证5马路上有编号为1，2，3，,，2005 的 2005 只路灯，为节约用电，现要求把其中的200 只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，求满足条件的关灯方法共有多少种？解：任意一种关灯的方法，都对应着一种满足题设条件的亮灯与暗灯的排列，于是总是转化为1805只亮灯中插入200 只暗灯，且任何两只暗灯不相邻，而且不在两

28、端，也就是在1805 只亮灯所形成的1804 个间隙中选200 个插入暗灯，其方法有2001804C种6把2005 个不加区别的小球分别放在10 个不同的盒子里，使得第i 个盒子中至少有i 个球)10,.,2,1(i，问不同放法的总数是多少？解：先在第i个盒子里放入i个球，这时共放了1+2+,+10=55 个球，还余下2005-55=1950 个球，故问题转化为把1950 个球任意放入10 个盒子（允许有的盒子不放球），相当于一个不定方程的非负整数解的个数问题，共有19501950910 1950 119591959CCC种7n个人)3(n站成一圈，其中某指定的两人A、B 肯定不相邻的站法有多

29、少种？答案：)!2(2)!1(nn8甲、乙两队各出7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由一号队员比赛，负者被淘汰，胜者再与负方2 号队员比赛，,，直到一方队员全部淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数是多少？解：不妨先设甲方胜出，则问题等价于求方程7.721xxx的非负整数解的个数，有6137177CC种，同理，乙方胜的比赛过程也有6137177CC种，故可能出现的比赛过程有6132C种9有男生mn人，女生m人（1,nm），（1）这mn2个人排成一列，女生不相邻，首尾都是男生，有多少种排法？（2）这mn2个人围成一圈，女生不相邻，有多少种排

30、法？解：（1）mmnAmn1)!(；（2）先作男生圆排列，然后插入，共mmnAmn)!1(10方程3.210321xxxx的非负整数解共有多少个？解：由题意，1,01x，故分情况讨论如下：若01x，则3.1032xxx，非负整数解的个数为：1653139C；若11x，则1.1032xxx，非负整数解的个数为：91119C综上，非负整数解的个数为：165+9=174 个11一个盒子里有7 个分别标有号码1，2，,，7 的球，每次取出一个，记下它的号码后再放回盒子，共取（放）4 次，求 4 次中最大标号恰是5 的取法数？解：最大标号为5，相当于从1，2，,，5 中取，共取（放）4 次，共有45种取

31、法；从中剔除四次中最大标号均不是5 的种数，结果为4544=36912已知集合2,|12nNnCzzzzAn，在复平面上，以A 中的复数的对应点为顶点可构成多少个直角三角形？解：易求得122,1,0nA，其中nie（n?2）设各复数在复平面上对应点依次为O、A0、A1、A2、,、A2n-1，则 A0A1A2,A2n-1为正 2n 边形，易知在jiAOA中以jiAA,为顶点的内角均为A B C D E F 锐角，所以，由O、A0、A1、A2、,、A2n-1为顶点的直角三角形可分为两类：第一类：以O 为直角顶点的直角三角形，不失一般性，可设900KOAA，则nk2，所以)(2Nkkn，这说明这类直角三角形存在当且仅当n 为偶数时，这时，这样的直角三角形有2n 个；第二类：不以O 为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上，即由A0、A1、A2、,、A2n-1构成，这些点可确定n 条直径，于是可构成)22(nn个直角三角形综上所述，由加法原理，所求直角三角形的总个数为为奇数为偶数nnnnnnnnnf),1(2,22)22()(2