8、排列组合问题

《8、排列组合问题》由会员分享，可在线阅读，更多相关《8、排列组合问题（6页珍藏版）》请在金锄头文库上搜索。

1、排列组合问题之涂色问题（四个方面）一、区域涂色问题1、根据分步计数原理，对各个区域分步涂色，这是处理区域染色问题的基本方法。例 1、用5种不同的颜色给图中标、的各部分涂色，每部分只涂一种颜色，相 邻部分涂不同颜色，则不同的涂色方法有多少种？解析：先给号区域涂色有5种方法；再给号涂色有4种方法；接着给号涂色方法 有3种方法；由于号与号、号不相邻，因此号有4种涂法。根据分步计数原理，不 同的涂色方法有5 x 4 x 3 x 4 = 240种。2、根据共用了多少种颜色讨论，分别计算出各种情形的种数，再用分类计数原理求出不同 的涂色方法种数。例2、 4种不同的颜色涂在如图所示的6个区域，且相邻两个区域

2、不能同色。解析：依题意只能选用4种颜色，要分四类：与同色、与同色，则有A4种;4与同色、与同色，则有A4种;4与同色、与同色，则有A4种;4与同色、与同色，则有A4种;4与同色、与同色，则有A4种。4根据分类计数原理得涂色方法总数为5 A4 = 120。4例3、 如图所示，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色。现有4种颜色可供选择，则不同的着色方法共有多少种? 解析：依题意至少要用3种颜色。 若用3种颜色，区域2与4必须同色， 区域3与5必须同色，故有A3种；4 若用4种颜色，则区域2与4同色， 区域3与5不同色，有A4种；或区域3与5同色，区域2与4不同色，有

3、A4种。共有2A4种。4 44根据分类计数原理得满足题意的着色方法共有A3 + 2A4 = 72。443、根据某两个不相邻区域是否同色分类讨论。从某两个不相邻区域同色与不同色入手，分 别计算出两种情形的种数，再用分类计数原理求出不同涂色方法总数。例 4 、 用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内，每个区域涂一种颜色 相邻两个区域涂不同的颜色，五种颜色可以反复使用，共有多少种不同的涂色方法? 解析：可把问题分为三类： 四格涂不同的颜色，有A3种；4 有且仅有两个区域颜色相同，即只有 一组对角小方格涂相同的颜色。涂法种数有 2C1C2；54 两组对角小方格分别涂相同的颜色，有A2种。

4、5根据分类计数原理得涂法种数共有A3 + 2C1C 2 + A2 = 260种。45 454、根据相间区域使用颜色分类讨论。例5 、如图， 6个扇形区域 A、B 、C 、D、E 、F ，现给这6 个区域着色，要求同一 区域涂同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种不同的颜色可以反复使用，共有多少种不同的涂色方法?解析：当相间区域A、C、E着同一种颜 色时，有4种着色方法，此时B、D、F各有3 种着色方法，共有4 x 3 x 3 x 3二108种方法。当相间区域A、C、E着两种不同 的颜色时，有C2A2种着色方法，此时B、D、F34有3x 2x 2种着色方法，共有C2A2 x 3x

5、 2x 2 = 432种方法。34 当相间区域A、C、E着三种不同的颜色时有A3种着色方法，此时B、D、4F各有2种着色方法，共有A3 x 2x2x2 = 192种方法。4总计有108 + 432 +192 = 732种不同的涂色方法。5、用数列递推公式解决扇形区域涂色问题。例6、把一个圆分成n(n 2)个扇形，每个扇形用红、白、蓝、黑四色之一染色，要求相分成n个扇形时的染色方法有a种，则 n即 a = 12。邻扇形不同色，有多少种不同的染色方法？ 解析：设n个扇形分别为A、A、A , 12n 当n = 2时A、A有A2 = 12种染色方法，124 当分成n个扇形时，A与不同色，A与A不同色，

6、A与A不同色，共有123n-1n4x3n-1种染色方法。由于A与A相邻，应排除A与A同色的情形。n1n1A与A同色时，可把A、A看成一个扇形，与前n - 2个扇形加在一起为n-1个扇 n1 形，此时有a种染色法。n-1a = 4 x 3 n -1 - ann -1a = -ann -1n1故有如下递推关系：+ 4 x 3n-1 = - (a+ 4 x 3n -2)+ 4 x 3n-1n-2/D= a-4x3n-2 +4x3n-1 = a+4x3n-3 -4x3n-2 +4x3n-1n一2n-3=4 x 3n-1 3n-2 + O x 3=(3 + 1)x 3n-1 3n一2 + + (-1x

7、3=3 x 卩“-1 一 3n-2 +(-1)n x 3 + 1 x3n-1 3n-2 + (-1)n x 3=卩“ 3n-1 + 3n - 2 + (-1)n x 32 +3n-1 - 3n-2 + (-1)n x 32 + (-1x 3=(-1)n x3+ 3n二、点涂色问题方法：根据共用了多少种颜色分类讨论；根据相对顶点是否同色分类讨论； 将空间问题平面化，转化为区域涂色问题。例 7、将一个四棱锥S - ABCD的每个顶点染上一种颜色，并使 同一条棱的两端点异色，如果只有5种颜色可供使用，那么不同的 染色方法的总数是多少？解法一：满足题设条件的染色至少要用3种颜色。 若恰用 3 种颜色，

8、可先从5 种颜色中任选一种染顶点S，再从余下的4种颜色中任选2种染A、B、 C、D四点，此时只能A与C、B与D分别同色，故 有Ci A2 = 60种方法。54 若恰用4种颜色，可以先从5种颜色中任选一种 染顶点S，再从余下的4种颜色中任选2种染A与B，由于A、B颜色可以交换，故有A2种染法；再从余下的2种颜色中任选1种染D或C，而4D与C中的另一个只需染与其相对顶点同色即可，故有CiA2C1C1 = 240种方法。5 4 2 2 若恰用5种颜色，有A5 = 120种方法。5综上，满足题意的染色方法数为60 + 240 +120 = 420种。解法二：设想染色按S - A - B - C - D

9、的顺序进行，对S、A、B染色，有5 x 4 x 3 = 60 种染色方法。由于C点的颜色可能与A同色或不同色，这影响到D点颜色的选取方法数， 故分类讨论：C与A同色时（此时C对颜色的选取方法唯一）， D应与A（ C ）、S不同色，有3种选择；C与A不同色时， C有2种选择的颜色，D也有2种颜色可选择，从而对C、D 染色有1x 3 + 2 x 2 = 7种染色方法。由分步计数乘法原理得，总 的染色方法数为60 x 7 = 420种。解法三：这个问题可转化成相邻区域不同色问题。如图，对这 五个区域用5种颜色涂色，有多少种不同的涂色方法？三、线段涂色问题方法：根据共用了多少颜色分类讨论。 根据相对线

10、段是否同色分类讨论。解决线段涂色问题，要特别注意对各条线段依次涂色。例8、用红、黃、蓝、白四种颜色涂矩形ABCD的四条边，每条边只涂一种颜色，且使相 邻两边涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？解法一：（1）使用四种颜色，有A4种；4 使用三种颜色，则必须将一组对边染成同色，故有C1C1A2种；423 使用二种颜色，则两组对边必须分别同色，有A2种；4 因此，染色方法共有A4 + C1C1A2 + A2 = 84种。44 2 34解法二：涂色按AB - BC - CD - DA的顺序进行，对AB、BC涂色有4 x 3 = 12种。 由于CD的颜色可能与AB同色或不同色，

11、这影响到DA颜色的选取，故分类讨论: 当CD与AB同色时，这时CD对颜色的选取唯一，则DA有3种颜色可选； 当CD与AB不同色时，CD有两种颜色可选，DA也有两种颜色可选.对CD、DA有1x3 + 2x2 = 7种涂色方法。 由分步计数乘法原理，总的涂色方法数为12 x 7 = 84种。例9、用六种颜色给正四面体A-BCD的每条棱染色，要求每条棱只染一种颜色且共顶点 的棱涂不同的颜色，问有多少种不同的涂色方法？解析：若恰用三种颜色，则每组对棱涂同色，组与组之间不同色，有A3种方法。6 若恰用四种颜色，则三组对棱中有二组对棱涂同色，有C2A4种方法。36 若恰用五种颜色，则三组对棱中有一组对棱涂

12、同色，有C1 A5种。36 若恰用六种颜色，则有A6种。6综上，总的染色方法数为A3 + C2A4 + C1A5 + A6 = 4080种。6 3 63 66四、面涂色问题例9 、从给定的六种不同颜色中选用若干种颜色，将一个正方体的 6 个面涂色，每两个具 有公共棱的面涂成不同的颜色，则不同的涂色方案共有多少种？ 解析：至少需要三种颜色，根据用了多少种颜色分类讨论。 用了六种颜色。确定某种颜色所涂面为下底面，则上底面颜色有5种选择，在上、下 底面已涂好后，再确定其余4 种颜色中的某一种所涂面为左侧面，则其余3个面有3!种涂色 方案。5x3! = 30种。 用了五种颜色。选定五种颜色有C5 =

13、6种，必有两面同色（必为相对面），确定为上、6下底面，其颜色可有5 种选择，再确定一种颜色为左侧面，此时的方案数取决于右侧面的颜 色，有3种选择（前后面可通过翻转交换）。n = C5 x5x3 = 90种。26 用了四种颜色。仿上分析可得n二C4C2二90种。364 用了三种颜色。仿上分析可得n = C3 = 20种。46综上，总的涂色方案数为n + n + n + n = 30 + 90 + 90 + 20 = 230种。1234例 10、四棱锥P- ABCD，用4种不同的颜色涂在四棱锥的各个面上，要求相邻不同色， 有多少种涂法？B解析：可转化为区域涂色问题。如右图，区域1、 2、 3、 4相当于四个侧面，区域5相当于底面。根据共用颜色多少分类：最少要用3种颜色，即1与3同色、2与4同色，有A: 种；当用4种颜色时，1与3、2与4两组中只能有一组同色，此时有C1 A4种。故涂色方法24总数为A3 + C1A4 = 72种。424例 11、用三种不同的颜色填涂右图3x3方格中的9个区域， 要求每行、每列的三个区域都不同色，则不同的填涂方法种 数共有（ D ）A、 48 B、 24 C 、 12 D、 6 解析：第一行（或列） 3 种；第二行（或列） 2 种；第三 行（或列）1种。共有3 x 2 x1 = 6种。