环形涂色与错位排列

1、浅析高二(下A)排列与组合中的两大难点摘要:本文对人民教育出版社出版的高二(下A)第十章排列与组合中的”环行涂色”和”错位排列”作了一定的完善,主要给出了”环行涂色”和”错位排列”的排列数的递推公式和通项公式,从而解决了高中生心目中对排列与组合部分的两大难点,使得他们面对这两种问题就能迎刃而解。关键词：环行涂色；错位排列；递推公式；通项公式中图分类号：O133The tray analyses two (go down A)high two big difficult point in rranging and constitutingYue chunhongTongliang middle

2、school , Chongqing 401331Abstract: Circumnavigation in arranging the main body of a book and constituting to two (go down A) tenth high chapters that the people's education press publishes " scribbles the color " and " the malposition arrangement " having done certain improvi

3、ng and perfecting, and the recursion formula having given circumnavigation out" the number of permutations scribbling the color " and " the malposition arrangement mainly" exchanging item formula, they face this two kinds problems will do in the mental view having resolved a high

4、 school student thereby to arranging two big difficult point of part and constituting, being therefore likely to be easily solved.Keywords: Annularity spreads a color, Malposition arrangement, Recursion formula,Arrange with combination一、引言“环行涂色”和“错位排列”在排列与组合中居于重要地位,尤其是在实际生活中的应用广泛存在。许多的规划及其方案问题都归结为“环

5、行涂色”与“错位排列”,因此给出”环行涂色”和“错位排列”的递推公式和通项公式是及其必要的。在现行的高中教材中都没有对”环行涂色”和”错位排列”做专题的研究，然而在习题中却大量出现，并且在高考试题中也是经常出现。本文在对教材的研究和大量习题的解答以及相关资料和文献的基础上，得出了“环行涂色”和“错位排列”的递推公式和通项公式，解决了广大高中生对排列与组合中两大难点。二、基础知识 （）环形涂色 环形涂色问题又称为多边形的涂色问题,在一般的题型中,可将题意抽象为环形涂色问题,该问题的一般化为：用m(m)种不同颜色给n边形各顶点涂色,且相邻顶点不同色,则不同的涂色方案有种 -定理一：设环形涂色的方案

6、数为，则的递推公式为AAAAAAA证明：如右图所示:在处有种涂色方案，在处有种涂色方案,此时考虑也有种涂色方案在此情况下有两种情况：情况一: A与A同色,此时相当于A与A重合,这时问题转化为种不同颜色给边形涂色,即为a种涂色方案;情况二:A与A不同色,此时问题就转化为用种不同颜色给边形的各顶点涂色,且相邻顶点不同色,即此时的情况就是。根据分类原理可知m(m-1)，且满足初始条件:=m(m-1)(m-2)即递推公式为定理二：设环形涂色的方案数为，则的通项公式为证明：根据定理一的递推公式，则有所以 所以 所以 例1: 用红、黄、蓝、白、黑五种颜色涂在“田字”形的4个小方格内，每格涂一种颜色，相邻两

7、格不同色，如果颜色可以重复使用，共有多少种不同的涂色方法？1243解：此题抽象为“涂色问题”故由定理可知 例2: 如图所示:某城市在中心654433321广场建造一个花圃, 花圃分为6个部分,现要栽种4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有多少种?解: 此问题也为“涂色问题”,根据“大度优先原则”对区域1,有C种涂色方案,对区域2,3,4,5,6就可以看作是“环行涂色问题”,即用3种颜色给涂色,且相邻区域的颜色不同,则由”环行涂色”问题可知a=(3-1)+(-1)(3-1)=32-2=30,所以总的涂色数为C30=120种.即不同的栽种方案为120种。（

8、二）、错位排列 定义：一般地，设排列是1，2，n，则 的一个错位排列就是排列,且，。定理一：设排列的错位排列数为，且，则满足下面的递推关系：证明：设，考虑排列1，2，n的所有的错位排列，根据在排列中的第一位的数字是2，n，而将这些排列划分成类，即有类，令表示第一位是2的错位排列数，则有。现在考虑中的排列，则是2的形式，其中。此时，若，则在这种情况下就是一个级的排列的错位排列，此时的排列数为，若，此时对于2中，则这种情况就是的一个级排列的错位排列，此时的排列数为，因此，从而，即，又因为满足初始条件，故定理一得证。定理二： 设排列的错位排列数为，且，则证明：由定理一知；当时，有 即 所以 所以 即 所以 所以 所以 所以 又因为 当时所以 例：同寝室四人写一张贺年卡，先集中起来，然后每人从中拿一张别人写的贺年卡，问这四张贺年卡有多少种不同的分配方式？解：这个问题就是一个错位排列，即每个人写的贺年卡不能给自己，由定理二知：三 、总结“环形涂色”与“错位排列”是排列与组合中的两大难点和重点，高考常考的题型。本文作者在对大量“环形涂色”与“错位排列”的研究后，再结合相关的资料和文献给出了递推公式和通项公式。但是本文没有对这类问题做更广泛的推广，这是本文的局限性，希望广大的读者能够做出更广泛的推广。 参考文献1屈婉玲，组合数学，M，北京， 北京大学出版社20072人民教育出版社中学数学室，