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

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

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

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

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

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