小學奧數專題--排列組合.doc

《小學奧數專題--排列組合.doc》由會員分享，可在線閱讀，更多相關《小學奧數專題--排列組合.doc（15頁珍藏版）》請在裝配圖網上搜索。

2 排列問題題型分類： 1.信號問題 2.數字問題 3.坐法問題 4.照相問題 5.排隊問題 2 組合問題題型分類： 1.幾何計數問題 2.加乘算式問題 3.比賽問題 4.選法問題 2 常用解題方法和技巧 1. 優(yōu)先排列法 2. 總體淘汰法 3. 合理分類和準確分步 4. 相鄰問題用捆綁法 5. 不相鄰問題用插空法 6. 順序問題用“除法” 7. 分排問題用直接法 8. 試驗法 9. 探索法 10. 消序法 11. 住店法 12. 對應法 13. 去頭去尾法 14. 樹形圖法 15. 類推法 16. 幾何計數法 17. 標數法 18. 對稱法 分類相加，分步組合，有序排列，無序組合 2 基礎知識（數學概率方面的基本原理） 一. 加法原理：做一件事情，完成它有N類辦法， 在第一類辦法中有M1中不同的方法， 在第二類辦法中有M2中不同的方法，……， 在第N類辦法中有Mn種不同的方法， 那么完成這件事情共有M1+M2+……+Mn種不同的方法。 二. 乘法原理：如果完成某項任務，可分為k個步驟， 完成第一步有n1種不同的方法， 完成第二步有n2種不同的方法，…… 完成第ｋ步有ｎｋ種不同的方法， 那么完成此項任務共有ｎ１×ｎ２×……×ｎｋ種不同的方法。 三. 兩個原理的區(qū)別 n 做一件事，完成它若有n類辦法，是分類問題，每一類中的方法都是獨立的，故用加法原理。 每一類中的每一種方法都可以獨立完成此任務；兩類不同辦法中的具體方法，互不相同(即分類不重)；完成此任務的任何一種方法，都屬于某一類(即分類不漏) n 做一件事，需要分n個步驟，步與步之間是連續(xù)的，只有將分成的若干個互相聯系的步驟，依次相繼完成，這件事才算完成，因此用乘法原理． 任何一步的一種方法都不能完成此任務，必須且只須連續(xù)完成這n步才能完成此任務；各步計數相互獨立；只要有一步中所采取的方法不同，則對應的完成此事的方法也不同 n 這樣完成一件事的分“類”和“步”是有本質區(qū)別的，因此也將兩個原理區(qū)分開來． 四. 排列及組合基本公式 1. 排列及計算公式 從n個不同元素中，任取m(m≤n)個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(m≤n)個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數，用符號 Pmn表示. Pmn =n(n-1)(n-2)……(n-m+1) = (規(guī)定0!=1). 2. 組合及計算公式 從n個不同元素中，任取m(m≤n)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n)個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數.用符號Cmn表示. Cmn = Pmn /m!= 一般當遇到m比較大時（常常是m>0.5n時），可用Cmn = Cn-mn 來簡化計算。 規(guī)定：Cnn =1, C0n=1. 3. n的階乘(n!)——n個不同元素的全排列 Pnn=n!=n×(n-1)×(n-2)…3×2×1 五. 兩個基本計數原理及應用 1. 首先明確任務的意義 【例1】 從1、2、3、……、20這二十個數中任取三個不同的數組成等差數列， 這樣的不同等差數列有________個。 分析：首先要把復雜的生活背景或其它數學背景轉化為一個明確的排列組合問題。 設a,b,c成等差，∴ 2b=a+c, 可知b由a,c決定， 又∵ 2b是偶數，∴ a,c同奇或同偶， 即：從1，3，5，……，19或2，4，6，8，……，20這十個數中 選出兩個數進行排列，由此就可確定等差數列， 如：a=1，ｃ=7，則b=4（即每一組a,c必對應唯一的b，另外1、4、7和7、4、1按同一種等差數列處理） ∴C210＝10×9＝90，同類（同奇或同偶）相加，即本題所求=2×90＝180。 【例2】 某城市有4條東西街道和6條南北的街道，街道之間的間距相同，如圖。 若規(guī)定只能向東或向北兩個方向沿圖中路線前進， 則從M到N有多少種不同的走法? 分析：對實際背景的分析可以逐層深入 （一） 從M到N必須向上走三步，向右走五步，共走八步。 （二）每一步是向上還是向右，決定了不同的走法。 （三）事實上，當把向上的步驟決定后，剩下的步驟只能向右。 從而，任務可敘述為：從八個步驟中選出哪三步是向上走，就可以確定走法數， ∴ 本題答案為：C38=56。 2. 注意加法原理與乘法原理的特點，分析是分類還是分步，是排列還是組合。 采用加法原理首先要做到分類不重不漏，如何做到這一點？分類的標準必須前后統(tǒng)一。 注意排列組合的區(qū)別與聯系：所有的排列都可以看作是先取組合，再做全排列； 同樣，組合如補充一個階段(排序)可轉化為排列問題。 【例3】 在一塊并排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟， 為有利于作物生長，要求A，B兩種作物的間隔不少于6壟，不同的選法共有______種。 分析：條件中“要求A、B兩種作物的間隔不少于6壟”這個條件不容易用一個包含排列數，組合數的式子表示，因而采取分類的方法。 第一類：A在第一壟，B有3種選擇； 第二類：A在第二壟，B有2種選擇； 第三類：A在第三壟，B有1種選擇， 同理A、B位置互換 ，共12種。 1．恰好能被6，7，8，9整除的五位數有多少個? 【分析與解】 6、7、8、9的最小公倍數是504，五位數中，最小的是10000，最大為99999． 因為10000÷504：19……424，99999÷504=198……207． 所以，五位數中，能被504整除的數有198-19=179個． 所以恰好能被6，7，8，9整除的五位數有179個． 2．小明的兩個衣服口袋中各有13張卡片，每張卡片上分別寫著1，2，3，…，13． 如果從這兩個口袋中各拿出一張卡片來計算它們所寫兩數的乘積，可以得到許多不相等的乘積． 那么，其中能被6整除的乘積共有多少個? 【分析與解】 這些積中能被6整除的最大一個是13×12=26×6，最小是6． 但在l×6～26×6之間的6的倍數并非都是兩張卡片上的乘積， 其中有25×6，23×6，21×6，19×6，17×6這五個不是． ∴所求的積共有26-5=21個． 3．1，2，3，4，5，6這6個數中，選3個數使它們的和能被3整除．那么不同的選法有幾種? 【分析與解】 被3除余1的有1，4； 被3除余2的有2,5； 能被3整除的有3，6． 從這6個數中選出3個數，使它們的和能被3整除， 則只能是從上面3類中各選一個，因為每類中的選擇是相互獨立的， ∴共有2×2×2=8種不同的選法． 4．同時滿足以下條件的分數共有多少個? ①大于，并且小于； ②分子和分母都是質數； ③分母是兩位數． 【分析與解】 由①知分子是大于1，小于20的質數． 如果分子是2，那么這個分數應該在與之間，在這之間的只有符合要求． 如果分子是3，那么這個分數應該在與之間，15與18之間只有質數17，所以分數是． 同樣的道理，當分子是5，7，11，13，17，19時可以得到下表． 分子 分數 分子 分數 2 11 3 13 5 17 7 19 于是，同時滿足題中條件的分數共13個． 5．一個六位數能被11整除，它的各位數字非零且互不相同的．將這個六位數的6個數字重新排列， 最少還能排出多少個能被11整除的六位數? 【分析與解】 設這個六位數為，則有、的差為0或11的倍數． 且、、、、、均不為0，任何一個數作為首位都是一個六位數． 先考慮、、偶數位內，、、奇數位內的組內交換，有×=36種順序； 再考慮形如這種奇數位與偶數位的組間調換，也有×=36種順序． 所以，用均不為0的、、、、、最少可以排出36+36=72個能被11整除的數(包含原來的)． 所以最少還能排出72-1=71個能被11整除的六位數． 6．在大于等于1998，小于等于8991的整數中，個位數字與十位數字不同的數共有多少個? 【分析與解】 先考慮2000～8999之間這7000個數，個位數字與十位數字不同的數共有7×10×=6300． 但是1998，8992～8998這些數的個位數字與十位數字也不同，且1998在1998～8991內，8992～8998這7個數不在1998～8991之內． 所以在1998～8991之內的個位數字與十位數字不同的有6300+1-7=6294個． 7．個位、十位、百位上的3個數字之和等于12的三位數共有多少個? 【分析與解】 12 = 0 + 6 + 6 = 0 + 5 + 7 = 0 + 4 + 8 = 0 + 3 + 9 = 1 + 5 + 6= 1 + 4 + 7 = 1 + 3 + 8 = 1 + 2 + 9 = 2 + 5 + 5 = 2 +4 + 6 = 2 + 3 + 7 = 2 + 2 + 8 = 3 + 4 + 5 = 3 + 3 + 6 = 4 + 4 + 4． 其中三個數字均不相等且不含0的有7組，每組有種排法，共7×=42種排法； 其中三個數字有只有2個相等且不含0的有3組，每組有÷2種排法，共有3×÷2=9種排法； 其中三個數字均相等且不含0的只有1組，每組只有1種排法； 在含有0的數組中，三個數字均不相同的有3組，每組有2種排法，共有3×2×=12種排法； 在含有0的數組中，二個數字相等的只有1組，每組有2÷2種排法，共有2種排法． 所以，滿足條件的三位數共有42 + 9 + 1 + 12 + 2 = 66個． 8．一個自然數，如果它順著看和倒過來看都是一樣的，那么稱這個數為“回文數”． 例如1331，7，202都是回文數，而220則不是回文數． 問：從一位到六位的回文數一共有多少個?其中的第1996個數是多少? 【分析與解】 我們將回文數分為一位、二位、三位、…、六位來逐組計算． 所有的一位數均是“回文數”，即有9個； 在二位數中，必須為形式的，即有9個(因為首位不能為0，下同)； 在三位數中，必須為(、可相同，在本題中，不同的字母代表的數可以相同)形式的， 即有9×10 =90個； 在四位數中，必須為形式的，即有9×10個； 在五位數中，必須為形式的，即有9×10×10=900個； 在六位數中，必須為形式的，即有9×10×10=900個． 所以共有9 + 9 + 90 + 90 + 900 + 900 = 1998個，最大的為999999，其次為998899，再次為997799． 而第1996個數為倒數第3個數，即為997799． 所以，從一位到六位的回文數一共有1998個，其中的第1996個數是997799． 9．一種電子表在6時24分30秒時的顯示為6:24，那么從8時到9時這段時間里， 此表的5個數字都不相同的時刻一共有多少個? 【分析與解】 設A:BC是滿足題意的時刻，有A為8，B、D應從0，1，2，3，4，5 這6個數字中選擇兩個不同的數字，所以有種選法，而C、E應從剩下的7個數字中 選擇兩個不同的數字，所以有種選法，所以共有×=1260種選法， 即從8時到9時這段時間里，此表的5個數字都不相同的時刻一共有1260個． 10．有些五位數的各位數字均取自1，2，3，4，5，并且任意相鄰兩位數字(大減小)的差都是1． 問這樣的五位數共有多少個? 【分析與解】 如下表，我們一一列出當首位數字是5，4，3時的情況． 首位數字 5 4 3 所 有 滿 足 題 意 的 數 字 列 表 滿足題意的數字個數 6 9 12 因為對稱的緣故，當首位數字為1時的情形等同與首位數字為5時的情形， 首位數字為2時的情形等同于首位數字為4時的情形． 所以，滿足題意的五位數共有6 + 9 + 12 + 9 + 6 = 42個． 11．用數字1，2組成一個八位數，其中至少連續(xù)四位都是1的有多少個? 【分析與解】 當只有四個連續(xù)的1時，可以為11112 * * *,211112 * * ,* 211112 *, * *211112，* * * 21111，因為 * 號處可以任意填寫1或2， 所以這些數依次有23，22，22，22，23個，共28個； 當有五個連續(xù)的l時，可以為111112 * * ，2111112 *，*2111112，* * 211111， 依次有22，2，2，22個，共12個； 當有六個連續(xù)的1時，可以為1111112 *，21111112，* 2111111，依次有2，1，2個，共5個； 當有七個連續(xù)的1時，可以為11111112，21111111，共2個： 當有八個連續(xù)的l時，只能是11111111，共1個． 所以滿足條件的八位數有28 + 12 + 5 + 2 + 1=48個． 12．在1001，1002，…，2000這1000個自然數中， 可以找到多少對相鄰的自然數，滿足它們相加時不進位? 【分析與解】 設為滿足條件的兩個連續(xù)自然數，有=+1． 我們只用考察的取值情況即可． 我們先不考慮數字9的情況(因為取9，則為0，也有可能不進位)， 則只能取0，1，2，3，4；只能取0，1，2，3，4；只能取0，1，2，3，4； 對應的有5×5×5=125組數． 當=9時，有的下一個數為，要想在求和時不進位，必須≤9， 所以此時只能取0，1，2，3，4；而也只能取0，1，2，3，4；共有5×5=25組數． 當=99時，有的下一個數為，要想在求和時不進位，必須+(+1)≤9， 所以此時只能取0，1，2，3，4；共有5組數． 所以，在1001，1002，…，2000這1000個自然數中，可以找到125 + 25 + 5 = 155對相鄰的自然數， 滿足它們相加時不進位． 13．把1995，1996，1997，1998，1999這5個數分別填入圖20-1中的東、南、西、北、中5個方格內， 使橫、豎3個數的和相等．那么共有多少種不同填法? 【分析與解】 顯然只要有“東”+“西”=“南”+“北”即可，剩下的一個數字即為“中”． 因為題中五個數的千位、百位、十位均相同，所以只用考慮個位數字， 顯然有5 + 9 = 6 + 8，5 + 8 = 6 + 7，6 + 9 = 7 + 8． 先考察5 + 9 = 6 + 8，可以對應為“東”+“西”=“南”+“北”，因為“東”、“西”可以調換，“南”、“北”可以對調，有2×2=4種填法，而“東、西”，“南、北”可以整體對調，于是有4×2=8種填法． 5 + 8 = 6 + 7，6 + 9 = 7 + 8同理均有8種填法，所以共有8×3=24種不同的填法． 14．在圖20-2的空格內各填人一個一位數，使同一行內左面的數比右面的數大，同一列內上面的數比下面的數小，并且方格內的6個數字互不相同，例如圖20-3為一種填法．那么共有多少種不同的填法? 2 3 圖20-2 6 4 2 7 5 3 圖20-3 【分析與解】 為了方便說明，標上字母： C D 2 A B 3 要注意到，A最大，D最小，B、C的位置可以互換． 但是，D只能取4，5，6，因為如果取7，就找不到3個比它大的一位數了． 當D取4，5，6時分別剩下5，4，3個一位大數．有B、C可以互換位置． 所有不同的填法共×2+×2+×2=10×2+4×2+1×2=30種． (2003年一零一中學小升初第12題)將一些數字分別填入下列各表中，要求每個小格中填入一個數字，表中的每橫行中從左到右數字由小到大，每一豎列中從上到下數字也由小到大排列． (1)將1至4填入表1中，方法有______________ 種： (2)將1至6填入表2中，方法有______________ 種； (3)將1至9填入表3中，方法有______________ 種． 【分析與解】 (1)2種：如圖，1和4是固定的，另外兩格任意選取，故有2種； (2)5種：1和6是固定的，其他的格子不確定．有如下5種： (3)42種：由(2)的規(guī)律已經知道，3×2是5種： 1、2、3確定后，剩下的6個格子是3×2，為5種．如下： 同理也各對應5種； 注意到 例外，對應的不是5種，因為第一排右邊的數限制了其下方的數字，滿足條件的只有如下幾種： 共計5 + 5 + 5 + 4 + 2 = 21種． 另外，將以上所有情況翻轉過來，也是滿足題意的排法，所以共21×2=42種． 15．從1至9這9個數字中挑出6個不同的數填在圖20－4的6個圓圈內， 使任意相鄰兩個圓圈內數字之和都是質數．那么共能找出多少種不同的挑法? (6個數字相同、排列次序不同的都算同一種．) 【分析與解】 顯然任意兩個相鄰圓圈中的數一奇一偶，因此，應從2、4、6、8中選3個數填入3個不相鄰的圓圈中． ：填入2、4、6，這時3與9不能同時填入(否則總有一個與6相鄰，和3+6或9+6不是質數)．沒有3、9的有1種；有3或9的，其他3個奇數l、5、7要去掉1個，因而有2×3=6種，共1+6＝7種． ：填入2、4、8．這時7不能填入(因為7+2，7+8都不是質數)，從其余4個奇數中選3個，有4種選法，都符合要求． ：填入2、6、8．這時7不能填入，而3與9只能任選1個，因而有2種選法． ：填入4、6、8．這時3與9只能任選1個，1與7也只能任選1個．因而有2×2=4種選法． 總共有7 + 4 + 2 + 4 = 17種選法 20．一個骰子六個面上的數字分別為0，1，2，3，4，5，現在擲骰子，把每次擲出的點數依次求和，當總點數超過12時就停止不再擲了，這種擲法最有可能出現的總點數是幾？ 1.???????? 從甲地到乙地有2種走法，從乙地到丙地有4種走法，從甲地不經過乙地到丙地有3種走法，則從甲地到丙地的不同的走法共有??????? 種． 2.???????? 甲、乙、丙3個班各有三好學生3，5，2名，現準備推選兩名來自不同班的三好學生去參加校三好學生代表大會，共有??????? 種不同的推選方法． 3.???????? 從甲、乙、丙三名同學中選出兩名參加某天的一項活動，其中一名同學參加上午的活動，一名同學參加下午的活動．有??????? 種不同的選法． 4.???????? 從a、b、c、d這4個字母中，每次取出3個按順序排成一列，共有??????? 種不同的排法． 5.???????? 若從6名志愿者中選出4人分別從事翻譯、導游、導購、保潔四項不同的工作，則選派的方案有??????? 種． 6.???????? 有a，b，c，d，e共5個火車站，都有往返車，問車站間共需要準備??????? 種火車票． 7.???????? 某年全國足球甲級聯賽有14個隊參加，每隊都要與其余各隊在主、客場分別比賽一場，共進行??????? 場比賽． 8.???????? 由數字1、2、3、4、5、6可以組成??????? 個沒有重復數字的正整數． 9.???????? 用0到9這10個數字可以組成??????? 個沒有重復數字的三位數． 10.???? （1）有5本不同的書，從中選出3本送給3位同學每人1本，共有 ???????種不同的選法； （2）有5種不同的書，要買3本送給3名同學每人1本，共有??????? 種不同的選法． 11.???? 計劃展出10幅不同的畫，其中1幅水彩畫、4幅油畫、5幅國畫，排成一行陳列，要求同一品種的畫必須連在一起，那么不同的陳列方式有??????? 種． 12.???? （1）將18個人排成一排，不同的排法有??????? 少種； （2）將18個人排成兩排，每排9人，不同的排法有??????? 種； （3）將18個人排成三排，每排6人，不同的排法有??????? 種． 13.???? 5人站成一排，（1）其中甲、乙兩人必須相鄰，有??????? 種不同的排法； （2）其中甲、乙兩人不能相鄰，有??????? 種不同的排法； （3）其中甲不站排頭、乙不站排尾，有??????? 種不同的排法． 14.???? 5名學生和1名老師照相，老師不能站排頭，也不能站排尾，共有??????? 種不同的站法． 15.???? 4名學生和3名老師排成一排照相，老師不能排兩端，且老師必須要排在一起的不同排法有??????? 種． 16.???? 停車場有7個停車位，現在有4輛車要停放，若要使3個空位連在一起，則停放的方法有??????? 種． 17.???? 在7名運動員中選出4名組成接力隊參加4×100米比賽，那么甲、乙都不跑中間兩棒的安排方法有??????? 種． 18.???? 一個口袋內裝有大小相同的7個白球和1個黑球．（1）從口袋內取出3個球，共有??????? 種取法； （2）從口袋內取出3個球，使其中含有1個黑球，有??????? 種取法； （3）從口袋內取出3個球，使其中不含黑球，有??????? 種取法． 19.???? 甲，乙，丙，丁4個足球隊舉行單循環(huán)賽： （1）共需比賽??????? 場； （2）冠亞軍共有??????? 種可能． 20.???? 按下列條件，從12人中選出5人，有??????? 種不同選法． （1）甲、乙、丙三人必須當選； （2）甲、乙、丙三人不能當選； （3）甲必須當選，乙、丙不能當選； （4）甲、乙、丙三人只有一人當選； （5）甲、乙、丙三人至多2人當選； （6）甲、乙、丙三人至少1人當選； 21.???? 某歌舞團有7名演員，其中3名會唱歌，2名會跳舞，2名既會唱歌又會跳舞，現在要從7名演員中選出2人，一人唱歌，一人跳舞，到農村演出，問有??????? 種選法． 22.???? 從6名男生和4名女生中，選出3名男生和2名女生分別承擔A，B，C，D，E五項工作，一共有??????? 種不同的分配方法． ?