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

淺析高二(下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)公式中圖分類號(hào)：O133The tray analyses two (go down A)high two big difficult point in rranging and constitutingYue chunhongTongliang middle school , Chongqing 401331Abstract: Circumnavigation in arranging the main body of a book and constituting to two (go down A) tenth high chapters that the peoples education press publishes scribbles the color and the malposition arrangement having done certain improving 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 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)行涂色”與“錯(cuò)位排列”,因此給出”環(huán)行涂色”和“錯(cuò)位排列”的遞推公式和通項(xiàng)公式是及其必要的。在現(xiàn)行的高中教材中都沒(méi)有對(duì)”環(huán)行涂色”和”錯(cuò)位排列”做專題的研究，然而在習(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)題又稱為多邊形的涂色問(wèn)題,在一般的題型中,可將題意抽象為環(huán)形涂色問(wèn)題,該問(wèn)題的一般化為：用m(m)種不同顏色給n邊形各頂點(diǎn)涂色,且相鄰頂點(diǎn)不同色,則不同的涂色方案有種 -定理一：設(shè)環(huán)形涂色的方案數(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ù)分類原理可知m(m-1)，且滿足初始條件:=m(m-1)(m-2)即遞推公式為定理二：設(shè)環(huán)形涂色的方案數(shù)為，則的通項(xiàng)公式為證明：根據(jù)定理一的遞推公式，則有所以 所以 所以 例1: 用紅、黃、藍(lán)、白、黑五種顏色涂在“田字”形的4個(gè)小方格內(nèi)，每格涂一種顏色，相鄰兩格不同色，如果顏色可以重復(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種。（二）、錯(cuò)位排列 定義：一般地，設(shè)排列是1，2，n，則 的一個(gè)錯(cuò)位排列就是排列,且，。定理一：設(shè)排列的錯(cuò)位排列數(shù)為，且，則滿足下面的遞推關(guān)系：證明：設(shè)，考慮排列1，2，n的所有的錯(cuò)位排列，根據(jù)在排列中的第一位的數(shù)字是2，n，而將這些排列劃分成類，即有類，令表示第一位是2的錯(cuò)位排列數(shù)，則有?，F(xiàn)在考慮中的排列，則是2的形式，其中。此時(shí)，若，則在這種情況下就是一個(gè)級(jí)的排列的錯(cuò)位排列，此時(shí)的排列數(shù)為，若，此時(shí)對(duì)于2中，則這種情況就是的一個(gè)級(jí)排列的錯(cuò)位排列，此時(shí)的排列數(shù)為，因此，從而，即，又因?yàn)闈M足初始條件，故定理一得證。定理二： 設(shè)排列的錯(cuò)位排列數(shù)為，且，則證明：由定理一知；當(dāng)時(shí)，有 即 所以 所以 即 所以 所以 所以 所以 又因?yàn)?當(dāng)時(shí)所以 例：同寢室四人寫一張賀年卡，先集中起來(lái)，然后每人從中拿一張別人寫的賀年卡，問(wèn)這四張賀年卡有多少種不同的分配方式？解：這個(gè)問(wèn)題就是一個(gè)錯(cuò)位排列，即每個(gè)人寫的賀年卡不能給自己，由定理二知：三 、總結(jié)“環(huán)形涂色”與“錯(cuò)位排列”是排列與組合中的兩大難點(diǎn)和重點(diǎn)，高考?？嫉念}型。本文作者在對(duì)大量“環(huán)形涂色”與“錯(cuò)位排列”的研究后，再結(jié)合相關(guān)的資料和文獻(xiàn)給出了遞推公式和通項(xiàng)公式。但是本文沒(méi)有對(duì)這類問(wèn)題做更廣泛的推廣，這是本文的局限性，希望廣大的讀者能夠做出更廣泛的推廣。 參考文獻(xiàn)1屈婉玲，組合數(shù)學(xué)，M，北京， 北京大學(xué)出版社20072人民教育出版社中學(xué)數(shù)學(xué)室，數(shù)學(xué)