■深圳技術(shù)大學附屬中學 邱崇洋

對于復(fù)雜的排列組合問題,必須講究解題方法。常言道:兵來將擋,水來土掩。那么,破解復(fù)雜的排列組合問題有哪些方法呢?

一、構(gòu)造模型法

例1馬路上有編號為1,2,3…,9這9盞路燈,現(xiàn)要關(guān)掉其中的3盞,但不能關(guān)掉相鄰的2盞或3盞,也不能關(guān)掉兩端的2盞,則滿足條件的關(guān)燈方案有多少種?

解析:把此問題當作一個排隊模型,在6盞亮燈的5個空隙中插入3盞不亮的燈,有種方法,所以滿足條件的關(guān)燈方案有10種。

點評:一些不易理解的排列組合題,如果能轉(zhuǎn)化為熟悉的模型(如占位填空模型、排隊模型、裝盒模型等),可使問題容易解決。

二、分解與合成法

例2(1)30 030能被多少個不同偶數(shù)整除?

(2)正方體8 個頂點可連成多少對異面直線?

解析:(1)先把30 030 分解成質(zhì)因數(shù)的形式:30 030=2×3×5×7×11×13。

依題意知偶因數(shù)2必取,再從3,5,7,11,13這5個因數(shù)中任取若干個相乘。

由此可見，會計內(nèi)容在與時俱進，變革速度很快，有可能給學生講授的財務(wù)會計內(nèi)容，還沒等學生畢業(yè)，所學內(nèi)容可能就已經(jīng)改變了，比如現(xiàn)在的經(jīng)融工具和收入的修改等。

(2)因為四面體中僅有3對異面直線,所以可將問題分解成正方體的8個頂點可構(gòu)成多少個不同的四面體。

所以8個頂點可連成的異面直線有3×58=174(對)。

點評:分解與合成策略是排列組合問題的一種最基本的解題策略。把一個復(fù)雜問題分解成幾個小問題逐一解決,然后依據(jù)問題分解后的結(jié)構(gòu),用分類計數(shù)原理和分步計數(shù)原理將問題合成,從而得到問題的答案,每個比較復(fù)雜的問題都要用到這種解題策略。

三、間接法

例38張卡片分別標數(shù)字1,2,3,4,5,6,7,8,從中取出6張卡片排成3行2 列,要求3行中僅有中間行的兩張卡片上的數(shù)字之和為5,則不同的排法共有( )。

A.1 344種 B.1 248種

C.1 056種 D.960種

解析:中間行數(shù)字之和為5 只有兩種情況,即1,4和2,3。但這兩組不能同時占據(jù)兩行,以1,4占中間行為例,則在安排時既要考慮另一組2,3是否同時被選中,還要考慮同時被選中時不能呆在同一行,情況比較復(fù)雜。所以考慮間接法,先求出中間數(shù)之和為5 的所有情況,再減去兩行和為5的情形。

先考慮中間和為5的所有情況:

再考慮兩行和為5的情況:

從而僅有中間行為5的情況有1 440-192=1 248(種),選B。

點評:對于復(fù)雜的排列組合問題,當從正面入手解決比較困難時,應(yīng)轉(zhuǎn)變思維角度,從反面考慮,這種方法體現(xiàn)了“正難則反”的解題思路。

四、轉(zhuǎn)化法

例4(1)平面上給定10個點,任意三點不共線,將10個點中的任意兩個點連成線段,求這些線段的交點個數(shù)(假設(shè)這些交點都不重合)。

(2)某火車站共設(shè)有4個安檢入口,每個入口每次只能進入1位乘客,求一個4 人小組進站的不同方案種數(shù)。

解析:(1)本題如果采用直接法,覺得無從下手,但注意到一個平面四邊形的對角線只有一個交點,那原問題可轉(zhuǎn)化為平面上10個無三點共線的點可以構(gòu)成多少個四邊形。所以這些線段的交點個數(shù)為=210。

(2)設(shè)4 名乘客中分別有z1,z2,z3,z4個人在第1個、第2個、第3 個、第4 個安檢口通過,則z1+z2+z3+z4=4,即問題轉(zhuǎn)化為求方程z1+z2+z3+z4=4的非負整數(shù)解的組數(shù),共有種情況,每一種進站情況的4個位置由4個人去站,有種方法。

所以一個4人小組進站的不同方案數(shù)為840。

點評:處理復(fù)雜的排列組合問題時可以把這個問題轉(zhuǎn)化成一個簡單的問題,通過解決這個簡單的問題從而解決原來的問題。

五、定序問題——除法倍縮法

例5甲、乙、丙、丁、戊這5 個人排成一排照相,且甲、乙不在丙的同側(cè),則不同的排法共有( )種。

A.48 B.40 C.60 D.64

解析:先對5人進行全排列,則不同的排法有種。由于甲、乙、丙的不同順序共有種,而甲、乙不在丙的同側(cè)的相對順序有甲→丙→乙和乙→丙→甲這兩種情況,占了總數(shù)的,故不同的排法共有(種)。選B。

點評:當n個人排成一列并且其中m人位置固定時,一般可先將n個人全排列,再除以m個人全排列總數(shù),即,這就是所謂的“除法倍縮”策略。