環(huán)形涂色與錯位排列

1、淺析高二(下A)排列與組合中的兩大難點摘要:本文對人民教育出版社出版的高二(下A)第十章排列與組合中的”環(huán)行涂色”和”錯位排列”作了一定的完善,主要給出了”環(huán)行涂色”和”錯位排列”的排列數(shù)的遞推公式和通項公式,從而解決了高中生心目中對排列與組合部分的兩大難點,使得他們面對這兩種問題就能迎刃而解。關(guān)鍵詞：環(huán)行涂色；錯位排列；遞推公式；通項公式中圖分類號：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一、引言“環(huán)行涂色”和“錯位排列”在排列與組合中居于重要地位,尤其是在實際生活中的應(yīng)用廣泛存在。許多的規(guī)劃及其方案問題都?xì)w結(jié)為“環(huán)

5、行涂色”與“錯位排列”,因此給出”環(huán)行涂色”和“錯位排列”的遞推公式和通項公式是及其必要的。在現(xiàn)行的高中教材中都沒有對”環(huán)行涂色”和”錯位排列”做專題的研究，然而在習(xí)題中卻大量出現(xiàn)，并且在高考試題中也是經(jīng)常出現(xiàn)。本文在對教材的研究和大量習(xí)題的解答以及相關(guān)資料和文獻的基礎(chǔ)上，得出了“環(huán)行涂色”和“錯位排列”的遞推公式和通項公式，解決了廣大高中生對排列與組合中兩大難點。二、基礎(chǔ)知識 （）環(huán)形涂色 環(huán)形涂色問題又稱為多邊形的涂色問題,在一般的題型中,可將題意抽象為環(huán)形涂色問題,該問題的一般化為：用m(m)種不同顏色給n邊形各頂點涂色,且相鄰頂點不同色,則不同的涂色方案有種 -定理一：設(shè)環(huán)形涂色的方案

6、數(shù)為，則的遞推公式為AAAAAAA證明：如右圖所示:在處有種涂色方案，在處有種涂色方案,此時考慮也有種涂色方案在此情況下有兩種情況：情況一: A與A同色,此時相當(dāng)于A與A重合,這時問題轉(zhuǎn)化為種不同顏色給邊形涂色,即為a種涂色方案;情況二:A與A不同色,此時問題就轉(zhuǎn)化為用種不同顏色給邊形的各頂點涂色,且相鄰頂點不同色,即此時的情況就是。根據(jù)分類原理可知m(m-1)，且滿足初始條件:=m(m-1)(m-2)即遞推公式為定理二：設(shè)環(huán)形涂色的方案數(shù)為，則的通項公式為證明：根據(jù)定理一的遞推公式，則有所以 所以 所以 例1: 用紅、黃、藍、白、黑五種顏色涂在“田字”形的4個小方格內(nèi)，每格涂一種顏色，相鄰兩

7、格不同色，如果顏色可以重復(fù)使用，共有多少種不同的涂色方法？1243解：此題抽象為“涂色問題”故由定理可知 例2: 如圖所示:某城市在中心654433321廣場建造一個花圃, 花圃分為6個部分,現(xiàn)要栽種4種不同顏色的花,每部分栽種一種且相鄰部分不能栽種同樣顏色的花,不同的栽種方法有多少種?解: 此問題也為“涂色問題”,根據(jù)“大度優(yōu)先原則”對區(qū)域1,有C種涂色方案,對區(qū)域2,3,4,5,6就可以看作是“環(huán)行涂色問題”,即用3種顏色給涂色,且相鄰區(qū)域的顏色不同,則由”環(huán)行涂色”問題可知a=(3-1)+(-1)(3-1)=32-2=30,所以總的涂色數(shù)為C30=120種.即不同的栽種方案為120種。（

8、二）、錯位排列 定義：一般地，設(shè)排列是1，2，n，則 的一個錯位排列就是排列,且，。定理一：設(shè)排列的錯位排列數(shù)為，且，則滿足下面的遞推關(guān)系：證明：設(shè)，考慮排列1，2，n的所有的錯位排列，根據(jù)在排列中的第一位的數(shù)字是2，n，而將這些排列劃分成類，即有類，令表示第一位是2的錯位排列數(shù)，則有?，F(xiàn)在考慮中的排列，則是2的形式，其中。此時，若，則在這種情況下就是一個級的排列的錯位排列，此時的排列數(shù)為，若，此時對于2中，則這種情況就是的一個級排列的錯位排列，此時的排列數(shù)為，因此，從而，即，又因為滿足初始條件，故定理一得證。定理二： 設(shè)排列的錯位排列數(shù)為，且，則證明：由定理一知；當(dāng)時，有 即 所以 所以 即 所以 所以 所以 所以 又因為 當(dāng)時所以 例：同寢室四人寫一張賀年卡，先集中起來，然后每人從中拿一張別人寫的賀年卡，問這四張賀年卡有多少種不同的分配方式？解：這個問題就是一個錯位排列，即每個人寫的賀年卡不能給自己，由定理二知：三 、總結(jié)“環(huán)形涂色”與“錯位排列”是排列與組合中的兩大難點和重點，高考?？嫉念}型。本文作者在對大量“環(huán)形涂色”與“錯位排列”的研究后，再結(jié)合相關(guān)的資料和文獻給出了遞推公式和通項公式。但是本文沒有對這類問題做更廣泛的推廣，這是本文的局限性，希望廣大的讀者能夠做出更廣泛的推廣。 參考文獻1屈婉玲，組合數(shù)學(xué)，M，北京， 北京大學(xué)出版社20072人民教育出版社中學(xué)數(shù)學(xué)室，