小學奧數(shù)專題--排列組合

1、排列問題題型分類：1. 信號問題2. 數(shù)字問題3. 坐法問題4. 照相問題5. 排隊問題組合問題題型分類：1. 幾何計數(shù)問題2. 加乘算式問題3. 比賽問題4. 選法問題常用解題方法和技巧1. 優(yōu)先排列法2. 總體淘汰法3. 合理分類和準確分步4. 相鄰問題用捆綁法5. 不相鄰問題用插空法6. 順序問題用“除法”7. 分排問題用直接法8. 試驗法9. 探索法10. 消序法11. 住店法12. 對應(yīng)法13. 去頭去尾法14. 樹形圖法15. 類推法16. 幾何計數(shù)法17. 標數(shù)法18. 對稱法分類相加，分步組合，有序排列，無序組合基礎(chǔ)知識 （數(shù)學概率方面的基本原理）一 . 加法原理： 做一件事情

2、， 完成它有 N 類辦法，在第一類辦法中有 M1 中不同的方法，在第二類辦法中有 M2 中不同的方法，在第 N 類辦法中有 Mn 種不同的方法，那么完成這件事情共有M1+M2+ +Mn 種不同的方法。二 . 乘法原理： 如果完成某項任務(wù)，可分為 k 個步驟，完成第一步有 n1 種不同的方法，完成第二步有 n2 種不同的方法，完成第步有 種不同的方法，那么完成此項任務(wù)共有 × ×× 種不同的方法。三 . 兩個原理的區(qū)別做一件事，完成它若有 n 類辦法，是分類問題 ，每一類中的方法都是 獨立的，故用加法原理。每一類中的每一種方法都可以獨立完成此任務(wù)；兩類不同辦法中的具

3、體方法，互不相同 ( 即分類不重 ) ；完成此任務(wù)的任何一種方法，都屬于某一類( 即分類不漏 )做一件事，需要分n 個步驟， 步與步之間是連續(xù)的，只有將分成的若干個互相聯(lián)系的步驟，依次相繼完成，這件事才算完成，因此用乘法原理任何一步的一種方法都不能完成此任務(wù)，必須且只須連續(xù)完成這n 步才能完成此任務(wù)；各步計數(shù)相互獨立；只要有一步中所采取的方法不同，則對應(yīng)的完成此事的方法也不同這樣完成一件事的分“類”和“ 步 ”是有本質(zhì)區(qū)別的，因此也將兩個原理區(qū)分開來四 . 排列及組合基本公式1. 排列及計算公式從 n 個不同元素中，任取 m(mn) 個元素按照 一定的順序 排成一列，叫做從 n 個不同元素中取

4、出 m個元素的一個 排列；從 n 個不同元素中取出 m(mn) 個元素的所有排列的個數(shù)，m叫做從 n 個不同元素中取出 m個元素的 排列數(shù)，用符號 Pn 表示 .m=n(n-1)(n-2) (n -m+1)P n=n!( 規(guī)定 0!=1) .(n-m)!2. 組合及計算公式從 n 個不同元素中，任取 m(mn) 個元素 并成一組 ，叫做從 n 個不同元素中取出 m個元素的一個組合；從 n 個不同元素中取出 m(mn) 個元素的所有組合的個數(shù)，叫做從n 個不同m元素中取出 m個元素的 組合數(shù) . 用符號 Cn 表示 .m= Pm/m!=n!Cn(n-m)!×m!nmn-m一般當遇到 m

5、比較大時（常常是 m>0.5n時），可用 Cn = Cn 來簡化計算。n0規(guī)定： C n =1, C n =1.3. n 的階乘 (n!) n 個不同元素的全排列nP n=n!=n ×(n-1) × (n-2) 3×2×1五 . 兩個基本計數(shù)原理及應(yīng)用1. 首先明確任務(wù)的意義【例 1】從 1、2、3、 20 這二十個數(shù)中任取三個不同的數(shù)組成等差數(shù)列，這樣的不同等差數(shù)列有_個。分析：首先要把復雜的生活背景或其它數(shù)學背景轉(zhuǎn)化為一個明確的排列組合問題。設(shè) a,b,c 成等差， 2b=a+c, 可知 b 由 a,c 決定，又 2b 是偶數(shù)， a,c 同奇或

6、同偶，即：從 1， 3， 5， 19 或 2， 4， 6， 8， 20 這十個數(shù)中選出兩個數(shù)進行排列，由此就可確定等差數(shù)列，如： a=1， =7，則 b=4（即每一組 a,c 必對應(yīng)唯一的 b，另外 1、4、7 和 7、 4、 1 按同一種等差數(shù)列處理） C210 10×990，同類（同奇或同偶）相加，即本題所求=2× 90180?！纠?2】某城市有 4 條東西街道和 6 條南北的街道，街道之間的間距相同，如圖。若規(guī)定只能向東或向北兩個方向沿圖中路線前進，則從 M到 N 有多少種不同的走法?分析：對實際背景的分析可以逐層深入（一）從 M 到 N 必須向上走三步，向右走五步，

7、共走八步。（二）每一步是向上還是向右，決定了不同的走法。（三）事實上，當把向上的步驟決定后，剩下的步驟只能向右。從而，任務(wù)可敘述為：從八個步驟中選出哪三步是向上走，就可以確定走法數(shù)， 本題答案為： C38=56 。2. 注意加法原理與乘法原理的特點，分析是分類還是分步，是排列還是組合。采用加法原理首先要做到分類不重不漏，如何做到這一點？分類的標準必須前后統(tǒng)一。注意排列組合的區(qū)別與聯(lián)系：所有的排列都可以看作是先取組合，再做全排列；同樣，組合如補充一個階段(排序 )可轉(zhuǎn)化為排列問題?！纠?3】在一塊并排的10 壟田地中，選擇二壟分別種植A ，B兩種作物，每種種植一壟，為有利于作物生長，要求A， B

8、兩種作物的間隔不少于6 壟，不同的選法共有_種。分析：條件中“要求A、B 兩種作物的間隔不少于6 壟”這個條件不容易用一個包含排列數(shù)，組合數(shù)的式子表示，因而采取分類的方法。第一類： A 在第一壟， B 有 3 種選擇；第二類： A 在第二壟， B 有 2 種選擇；第三類： A 在第三壟， B 有 1 種選擇，同理 A 、B 位置互換，共 12 種。1 恰好能被 6， 7， 8， 9 整除的五位數(shù)有多少個?【分析與解】 6 、 7、 8、 9 的最小公倍數(shù)是504，五位數(shù)中，最小的是10000，最大為 99999因為 10000÷504：19 424，99999÷504=19

9、8 207所以，五位數(shù)中，能被504 整除的數(shù)有198-19=179 個所以恰好能被6， 7， 8，9 整除的五位數(shù)有179 個2小明的兩個衣服口袋中各有13 張卡片，每張卡片上分別寫著1， 2，3， 13如果從這兩個口袋中各拿出一張卡片來計算它們所寫兩數(shù)的乘積，可以得到許多不相等的乘積那么，其中能被6 整除的乘積共有多少個?【分析與解】這些積中能被6 整除的最大一個是13×12=26×6，最小是6但在 l ×626×6 之間的 6 的倍數(shù)并非都是兩張卡片上的乘積，其中有 25×6，23×6，21×6，19×6，1

10、7×6 這五個不是 所求的積共有 26-5=21 個3 1，2， 3， 4， 5， 6 這 6 個數(shù)中，選3 個數(shù)使它們的和能被3 整除那么不同的選法有幾種?【分析與解】被3除余 1的有 1，4；被 3除余 2的有 2,5；能被 3 整除的有3， 6從這 6 個數(shù)中選出3 個數(shù)，使它們的和能被3 整除，則只能是從上面3 類中各選一個，因為每類中的選擇是相互獨立的， 共有 2× 2× 2=8 種不同的選法4 同時滿足以下條件的分數(shù)共有多少個?大于 1 ，并且小于 1 ；分子和分母都是質(zhì)數(shù)；分母是兩位數(shù)65【分析與解】由知分子是大于1，小于 20 的質(zhì)數(shù)如果分子是2，

11、那么這個分數(shù)應(yīng)該在2 與 2 之間，在這之間的只有2符合要求10811如果分子是 3，那么這個分數(shù)應(yīng)該在3與 3之間， 15 與 18之間只有質(zhì)數(shù)17，所以分數(shù)是3 151817同樣的道理，當分子是5， 7， 11， 13， 17， 19 時可以得到下表分子分數(shù)分子分數(shù)221111,11115961331313,13,1317677173551717,17298997737191937,9741于是，同時滿足題中條件的分數(shù)共13 個5一個六位數(shù)能被11 整除，它的各位數(shù)字非零且互不相同的將這個六位數(shù)的最少還能排出多少個能被11 整除的六位數(shù)?6 個數(shù)字重新排列，【分析與解】設(shè)這個六位數(shù)為abc

12、def，則有(ace) 、 (bdf ) 的差為0 或11 的倍數(shù)且 a 、 b 、 c 、 d 、 e、 f 均不為 0，任何一個數(shù)作為首位都是一個六位數(shù)先考慮 a 、 c 、 e 偶數(shù)位內(nèi)， b 、 d 、 f 奇數(shù)位內(nèi)的組內(nèi)交換，有P33 × P33=36 種順序；再考慮形如 badcfe 這種奇數(shù)位與偶數(shù)位的組間調(diào)換，也有33P3 × P3 =36 種順序所以，用均不為0 的 a 、 b 、 c 、 d 、 e 、 f 最少可以排出36+36=72 個能被 11 整除的數(shù) ( 包含原來的 abcdef ) 所以最少還能排出72-1=71 個能被 11 整除的六位數(shù)6

13、在大于等于 1998 ，小于等于 8991 的整數(shù)中，個位數(shù)字與十位數(shù)字不同的數(shù)共有多少個?【分析與解】先考慮 2000 8999 之間這 7000 個數(shù)，個位數(shù)字與十位數(shù)字不同的數(shù)共有2=63007×10× P10但是 1998，8992 8998 這些數(shù)的個位數(shù)字與十位數(shù)字也不同，且1998 在 1998 8991 內(nèi)， 8992 8998 這 7 個數(shù)不在 1998 8991 之內(nèi)所以在 1998 8991 之內(nèi)的個位數(shù)字與十位數(shù)字不同的有6300+1-7=6294 個7 個位、十位、百位上的3 個數(shù)字之和等于12 的三位數(shù)共有多少個 ?【分析與解】 12=0+6+6

14、=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其中三個數(shù)字均不相等且不含0的有 7組，每組有 P33 種排法，共 7× P33=42 種排法；其中三個數(shù)字有只有 2 個相等且不含 0的有 3 組，每組有 P33 ÷2種排法，共有3× P33 ÷ 2=9 種排法；其中三個數(shù)字均相等且不含0的只有 1組，每組只有 1 種排法；在含有 0 的數(shù)組中，三個數(shù)字均不相同的有3 組，每組有2 P22 種排法，共有3× 2× P

15、22=12 種排法；在含有 0 的數(shù)組中，二個數(shù)字相等的只有1 組，每組有 2P22 ÷2種排法，共有 2 種排法所以，滿足條件的三位數(shù)共有42+9+1+12+2=66個8一個自然數(shù)，如果它順著看和倒過來看都是一樣的，那么稱這個數(shù)為“回文數(shù)”例如 1331， 7， 202 都是回文數(shù)，而220則不是回文數(shù)問：從一位到六位的回文數(shù)一共有多少個?其中的第 1996個數(shù)是多少 ?【分析與解】我們將回文數(shù)分為一位、二位、三位、六位來逐組計算所有的一位數(shù)均是“回文數(shù)”，即有9 個；在二位數(shù)中，必須為aa 形式的，即有9 個 ( 因為首位不能為0，下同 ) ；在三位數(shù)中，必須為aba ( a 、

16、 b 可相同，在本題中，不同的字母代表的數(shù)可以相同) 形式的，即有 9×10 =90 個；在四位數(shù)中，必須為abba 形式的，即有 9× 10 個；在五位數(shù)中，必須為abcba 形式的，即有9× 10× 10=900 個；在六位數(shù)中，必須為abccba 形式的，即有9×10×10 =900 個所以共有 9+9+90+90+900+900=1998個，最大的為999999，其次為998899，再次為 997799而第 1996 個數(shù)為倒數(shù)第 3 個數(shù)，即為 997799所以，從一位到六位的回文數(shù)一共有1998個，其中的第 1996 個數(shù)

17、是 9977999 一種電子表在6 時 24 分 30 秒時的顯示為6:24 30 ，那么從8 時到 9 時這段時間里，此表的 5 個數(shù)字都不相同的時刻一共有多少個?【分析與解】設(shè) A:BC DE 是滿足題意的時刻，有A 為 8，B、 D 應(yīng)從 0， 1，2， 3， 4， 5這 6 個數(shù)字中選擇兩個不同的數(shù)字，所以有P62種選法，而 C、 E 應(yīng)從剩下的7 個數(shù)字中選擇兩個不同的數(shù)字，所以有P72 種選法，所以共有 P62 × P72=1260 種選法，即從 8 時到 9 時這段時間里，此表的5 個數(shù)字都不相同的時刻一共有1260 個10有些五位數(shù)的各位數(shù)字均取自1， 2， 3， 4

18、，5，并且任意相鄰兩位數(shù)字( 大減小 ) 的差都是1問這樣的五位數(shù)共有多少個?【分析與解】如下表，我們一一列出當首位數(shù)字是5， 4，3 時的情況首位數(shù)字543所有滿足題意的數(shù)字列表55545545454433545544443534333444332221313345224331232211321滿足題意的6912數(shù)字個數(shù)因為對稱的緣故，當首位數(shù)字為1 時的情形等同與首位數(shù)字為5 時的情形，首位數(shù)字為2 時的情形等同于首位數(shù)字為4 時的情形所以，滿足題意的五位數(shù)共有6+9+12+9+6=42個11 用數(shù)字 1， 2 組成一個八位數(shù)，其中至少連續(xù)四位都是1 的有多少個 ?【分析與解】當只有四個連

19、續(xù)的 1 時，可以為 11112 * * *,211112 * * ,* 211112 *,* *211112，* * * 21111 ，因為 *號處可以任意填寫 1 或 2，所以這些數(shù)依次有 23， 22， 22，22， 23 個，共 28 個；當有五個連續(xù)的l時，可以為111112 * * ， 2111112 * ， *2111112 ， * * 211111，22依次有 2 ，2，2， 2 個，共 12 個；當有六個連續(xù)的1時，可以為1111112 * ， 21111112， * 2111111 ，依次有 2， 1，2 個，共 5 個；當有七個連續(xù)的1時，可以為11111112， 211

20、11111，共 2 個：當有八個連續(xù)的l時，只能是11111111，共 1 個所以滿足條件的八位數(shù)有 28 + 12 + 5 + 2 + 1=48個12在 1001， 1002， 2000 這 1000 個自然數(shù)中，可以找到多少對相鄰的自然數(shù)，滿足它們相加時不進位?【分析與解】設(shè) 1bcd , xyzw為滿足條件的兩個連續(xù)自然數(shù)，有xyzw =1bcd +1我們只用考察1bcd 的取值情況即可我們先不考慮數(shù)字9 的情況 ( 因為 d 取 9，則 w 為 0，也有可能不進位) ，則 d 只能取 0， 1， 2，3， 4； c 只能取 0， 1， 2，3， 4； b 只能取 0，1， 2， 3，4

21、；對應(yīng)的有 5×5×5=125 組數(shù)當 d =9 時，有 1bc9 的下一個數(shù)為 1b(c 1)0 ，要想在求和時不進位，必須c ( c 1) 9，所以 c 此時只能取 0， 1，2， 3， 4；而 b 也只能取 0，1， 2， 3，4；共有 5× 5=25 組數(shù)當 cd=99時，有 1b99 的下一個數(shù)為 1(b 1)00 ，要想在求和時不進位，必須b +( b +1) ，9所以 b 此時只能取 0， 1， 2，3， 4；共有 5 組數(shù)所以，在1001， 1002， 2000 這 1000 個自然數(shù)中，可以找到 125 + 25 + 5 = 155對相鄰的自然數(shù)

22、，滿足它們相加時不進位13把 1995， 1996，1997， 1998， 1999 這 5 個數(shù)分別填入圖20-1 中的東、南、西、北、中5 個方格內(nèi)，使橫、豎3 個數(shù)的和相等那么共有多少種不同填法?【分析與解】顯然只要有“東” +“西” =“南” +“北”即可，剩下的一個數(shù)字即為“中”因為題中五個數(shù)的千位、百位、十位均相同，所以只用考慮個位數(shù)字，顯然有 5+9=6+8 ，5+8=6+7 ，6+9=7+8 先考察 5 + 9 =6 + 8，可以對應(yīng)為“東” +“西” =“南” +“北”，因為“東”、“西”可以調(diào)換，“南”、“北”可以對調(diào)，有2×2=4 種填法，而“東、西”，“南、北

23、”可以整體對調(diào)，于是有4×2=8 種填法5 + 8 = 6 + 7， 6 + 9 = 7 + 8同理均有8 種填法，所以共有8×3=24 種不同的填法14 在圖 20-2 的空格內(nèi)各填人一個一位數(shù)，使同一行內(nèi)左面的數(shù)比右面的數(shù)大，同一列內(nèi)上面的數(shù)比下面的數(shù)小，并且方格內(nèi)的6 個數(shù)字互不相同，例如圖20-3 為一種填法那么共有多少種不同的填法?23圖 20-2642753圖 20-3【分析與解】為了方便說明，標上字母：CD2AB3要注意到， A 最大， D 最小， B、 C 的位置可以互換但是， D 只能取 4， 5， 6，因為如果取7，就找不到3 個比它大的一位數(shù)了當 D取

24、 4，5， 6 時分別剩下5，4， 3 個一位大數(shù)有B、 C可以互換位置所有不同的填法共C53 × 2+ C43 × 2+ C33 × 2=10 × 2+4 × 2+1×2=30 種補充選講問題(2003 年一零一中學小升初第 12 題) 將一些數(shù)字分別填入下列各表中， 要求每個小格中填入一個數(shù)字， 表中的每橫行中從左到右數(shù)字由小到大，每一豎列中從上到下數(shù)字也由小到大排列(1) 將 1 至 4 填入表 1 中，方法有 _ 種：(2) 將 1 至 6 填入表 2 中，方法有 _ 種；(3) 將 1 至 9 填入表 3 中，方法有 _ 種

25、【分析與解】(1)2種：如圖， 1 和 4 是固定的，另外兩格任意選取，故有2 種；(2)5 種： 1 和 6 是固定的，其他的格子不確定有如下5 種：(3)42種：由 (2) 的規(guī)律已經(jīng)知道， 3×2 是 5 種：1 、 2、 3 確定后，剩下的6 個格子是3×2，為 5 種如下：同理也各對應(yīng)5 種；注意到例外，對應(yīng)的不是5 種，因為第一排右邊的數(shù)限制了其下方的數(shù)字，滿足條件的只有如下幾種：共計 5+5+5+4+2=21種另外，將以上所有情況翻轉(zhuǎn)過來，也是滿足題意的排法，所以共21×2=42 種15 從 1 至 9 這 9 個數(shù)字中挑出6 個不同的數(shù)填在圖20

26、4 的 6 個圓圈內(nèi)，使任意相鄰兩個圓圈內(nèi)數(shù)字之和都是質(zhì)數(shù)那么共能找出多少種不同的挑法?(6 個數(shù)字相同、排列次序不同的都算同一種)【分析與解】顯然任意兩個相鄰圓圈中的數(shù)一奇一偶，因此，應(yīng)從2、4、 6、8 中選 3 個數(shù)填入 3 個不相鄰的圓圈中第一種情況：填入 2、4、6，這時 3 與 9 不能同時填入 ( 否則總有一個與6 相鄰，和 3+6 或 9+6 不是質(zhì)數(shù) ) 沒有 3、 9 的有 1 種；有 3 或 9 的，其他 3 個奇數(shù) l 、 5、 7 要去掉 1 個，因而有2× 3=6 種，共 1+6 7 種第二種情況：填入 2、 4、 8這時 7 不能填入 ( 因為 7+2，

27、7+8 都不是質(zhì)數(shù) ) ，從其余4 個奇數(shù)中選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一個骰子六個面上的數(shù)字分別為0，1，2，3，4， 5，現(xiàn)在擲骰子，把每次擲出的點數(shù)依次求和，當總點數(shù)超過12 時就停止不再擲了，這種擲法最有可能出現(xiàn)的總點數(shù)是幾？1.從甲地到乙地有2 種走法，從乙地到丙地有4 種走法，從甲地不經(jīng)過乙地到丙地有3 種走法，

28、則從甲地到丙地的不同的走法共有種2. 甲、乙、丙 3 個班各有三好學生 3，5， 2 名，現(xiàn)準備推選兩名來自不同班的三好學生去參加校三好學生代表大會，共有種不同的推選方法3. 從甲、乙、丙三名同學中選出兩名參加某天的一項活動，其中一名同學參加上午的活動，一名同學參加下午的活動有種不同的選法4.從 a、b、 c、 d 這 4 個字母中，每次取出3 個按順序排成一列，共有種不同的排法5.若從 6 名志愿者中選出4 人分別從事翻譯、 導游、導購、保潔四項不同的工作，則選派的方案有種6.有 a，b， c， d，e 共 5 個火車站，都有往返車，問車站間共需要準備種火車票7.某年全國足球甲級聯(lián)賽有14 個隊參加，每隊都要與其余各隊在主、客場分別比賽一場，共進行場比賽8.由數(shù)字 1、 2、 3、 4、 5、6 可以組成個沒有重復數(shù)字的正整數(shù)9.用 0 到 9 這 10 個數(shù)字可以組成個沒有重復數(shù)字的三位數(shù)10.（ 1）有 5 本不