映射與計數(shù)在解競賽題中的應(yīng)用.doc

《映射與計數(shù)在解競賽題中的應(yīng)用.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、學(xué)科：奧數(shù)年級：高一?本周教學(xué)內(nèi)容：映射與計數(shù)在解競賽題中的應(yīng)用【內(nèi)容綜述】　　利用映射來解決計數(shù)問題，就是通過建立集合A與另一集合B之間的映射，把對集合A的計數(shù)轉(zhuǎn)移到對集合B的計數(shù)。實現(xiàn)這種轉(zhuǎn)移的關(guān)鍵是：（1）選擇適當(dāng)?shù)谋阌谟嫈?shù)的集合；（2）建立集合間的映射關(guān)系?！　≡O(shè)f：是集合A到集合B上的映射，那么　?。?）若f為單射，則。　?。?）若f為滿射，則?！　。?）若f為一一映射，則?！纠}分析】　　例1從的棋盤中，取出一個由三個小方格組成的L形，有多少種不同取法？這里棋盤是指m條橫線與n條豎線所構(gòu)成的棋盤。　　　　　　　　　解每種取法，都有一個點與它對應(yīng)，這個點就

2、是所取L形中三個小方格的公共點（如圖1），它是棋盤上橫線與豎線的交點，且不在棋盤的邊界上。從圖2可看出，每個點對應(yīng)于4種不同取法，這4種取法構(gòu)成一個“田”字形。而每個“田”字形都有唯一的中心。（例如點B），即映射f：“田”字形→“田”字形中心，是棋盤上由小方格組成的“田”字集合到棋盤內(nèi)橫線與豎線的交點集（不包括邊界上的點）的一一映射?！　★@然棋盤內(nèi)橫線與豎線的交點有個，所以，共有種不同取法?！　±?求n元集合A的所有子集的個數(shù)　　解設(shè)集合A的所有子集的集合為P（A），B為集合A到集合的全體映射的集合，對于任意的，可唯一確定一個從集合A到集合的映射　　　?。ㄍǔ７Q為集

3、合M的特征函數(shù)），即有唯一的與M對應(yīng)。　　反過來，對于任意的，有唯一的集合。顯然，且就是。因此，映射f：是集合P（A）到B的一一映射?！　∮捎趎元素集A到集合的映射的個數(shù)為，即，根據(jù)對應(yīng)原理　　　　說明一般地，集合到集合的所有映射的個數(shù)為。　　例3中日圍棋擂臺賽，雙方各派6名隊員按預(yù)定順序出場，直到最后一方取勝，問可能出現(xiàn)的比賽過程種數(shù)有多少種？　　解設(shè)中國隊員對應(yīng)紅球，日方隊員對應(yīng)白球。將被淘汰隊員對應(yīng)的球按被淘汰的時間順序一一排列出來。負(fù)方隊員全部被淘汰，則相應(yīng)球全部排出，然后將勝方所剩隊員對應(yīng)的球依次排在后面。由于雙方隊員出場順序已定，故可設(shè)同色球之間無區(qū)別，

4、于是一種比賽過程就對應(yīng)于6個紅球和6個白球的一種排列；反之，6個紅球和6個白球的一種排列對應(yīng)著一種比賽過程，即球的不同排列與不同比賽過程之間存在一一對應(yīng)關(guān)系。6個紅球和6個白球的不同排列數(shù)為，此即所求比賽過程種數(shù)?！　≌f明在某種映射下，兩個集合元素間一一對應(yīng)，該映射即為一一映射，所以對于明顯的一一映射只須指出兩集合間的一一對應(yīng)關(guān)系，就可運用對應(yīng)原理?！　±?求m元方程的正整數(shù)解的組數(shù)。　　解法一由于數(shù)組中各數(shù)可以重復(fù)，且大小無序，因此作如下映射：　　　　顯然①　　且一一對應(yīng)，所以，映射　　是一一映射?！　∫驗椋瑵M足①的數(shù)組有個，所以所求方程解的組數(shù)為?！　〗夥ǘ紤]

5、長度為n的線段AB。方程的任一組解對應(yīng)于把線段分成m節(jié)的一種分法，其中第一節(jié)的長度為，第二節(jié)的長度為，…，第m節(jié)的長度為，而每一種分法又對應(yīng)于線段長n-1個分點中取出m-1個分點的一種取法。反過來，線段n-1個分點中取出m-1個分點的任一種取法，都把線段AB分成m節(jié)。令依次取m節(jié)的長度，就得到方程的一組解?！　∷?，原方程解的組數(shù)就是線段AB上n-1個分點中取出m-1個的不同取法的種數(shù)?！　≌f明若把問題改為：求m元方程的非負(fù)整數(shù)解的組數(shù)，只要令，則化為求方程的正整數(shù)解的組數(shù)，由例4可知所求解的組數(shù)為?！　±?設(shè)為A的三元子集，若滿足為A的“好子集”，求A的“好子集”

6、的個數(shù)。　　解令　　　　　　作映射?！　是到上的一一映射。事實上，當(dāng)時，，那么即。　　另一方面，若，則，即?！　∮谑怯蓪?yīng)原理，，即A的“好子集”有個?！　±?設(shè)n為正整數(shù)，若的一個排列中存在，使成立，則稱該排列具有性質(zhì)P。證明：具有性質(zhì)P的排列比不具有性質(zhì)P的排列多。　　證明設(shè)A是由不具有性質(zhì)P的排列構(gòu)成的集合，B是恰有一對滿足的排列構(gòu)成的集合，C是具有性質(zhì)P的所有排列構(gòu)成的集合，顯然，從而。設(shè)，其中必有一個，使，于是調(diào)整的位置如下，該排列僅有一對相鄰數(shù)滿足，從而。上述調(diào)整構(gòu)成了一個A到B的映射，因此，。又，故，即具有性質(zhì)P的排列比不具有性質(zhì)P的排列多?！　±?

7、已知，，并且①②　　求的個數(shù)?！　〗庥散谥杏衝個+1，n個-1，這樣的有序數(shù)組有個。下面考慮這樣的有序數(shù)組中有多少不符合①，設(shè)其個數(shù)為。　　如果不符合①，那么一定存在最小的自然數(shù)，滿足　?。?）；　?。?）　　將統(tǒng)統(tǒng)改變符號，這一對應(yīng)改為n+1個+1，n-1個-1組成的有序數(shù)組。　　反之，對于任何一個n+1個+1，n-1個-1組成的有序數(shù)組，由于+1多于-1，必然存在一個最小的自然數(shù)s，滿足。　　將變?yōu)?，就得到一個n個+1，n個-1組成的不符合①的有序數(shù)組，所以，f是一一映射，由對應(yīng)原理知等于n+1個+1，n-1個-1組成的有序數(shù)組的個數(shù)，即?！　∫虼?，符合題