用對應思想解排列組合題

王榮峰(特級教師)

所謂對應思想就是在兩個事物之間建立起來的一種關系,即對應關系,從而揭示事物之間的聯系,它是解決數學問題的一種基本思想和策略.本文就對應思想在解排列組合題中的主要應用進行盤點,以期能對大家解題能力的提升有所幫助.

1 元素分配問題

例1全集U={1,2,3,4,5,6,7},集合A,B都是U的子集,若A∩B={2,4,6},則稱A,B為“理想配集”,記作(A,B),這樣的“理想配集”共有( )個.

A. 15 B. 16

C. 81 D. 82

解析 如圖1所示，分別用兩個橢圓的內部表示集合A與B，因為A∩B={2,4,6}，所以2,4,6必須選擇區域Ⅱ;對于1,3,5,7,每個數都可選擇Ⅰ,Ⅲ,Ⅳ3個區域中的任意1個,由分步計數原理知，共有3×3×3×3=81種不同的選擇方式,且每一種選擇方式都有唯一對應的一個集合對(A,B),即相應的集合對(A,B)共有81對. 選C.

圖1

點評 該題并不復雜,挖掘“理想配集”的定義,借助分步計數原理先計算出自由元素1,3,5,7有多少種分配方式,然后再進行合理對應,問題便可獲解,即先分步,再對應.

2 共點方格問題

例2在m×n(m,n≥3,m,n∈N*)的棋盤上取兩個小方格,若這兩個小方格恰有一個公共點,則不同的取法共有( )種.

A.mn

B. 2mn

C. (m-1)(n-1)

D. 2(m-1)(n-1)

圖2

解析 從圖2可以看出,每個公共點P都對應兩種不同的取法,即取兩個黑格或兩個白格.由于在m×n的棋盤內部的m-1條橫線與n-1條豎線共對應了(m-1)·(n-1)個交點,所以滿足條件的取法共有2(m-1)·(n-1)種. 選D.

點評 注意到每個公共點P都對應兩種不同的取法,進而可將問題等價轉化為求棋盤內橫豎線對應的交點問題,從而找到問題解決的切入點,即先對應,再對應.

3 最短路徑問題

例3如圖3,坐標平面內有一質點P從原點O出發,目標是點M(5,4),若質點P每次只能沿坐標軸移動1個單位,則它到達目標點M的最短路徑共有( )條.

圖3

A. 9 B. 20

C. 126 D. 1 024

點評 弄清質點P從O到M的“最短路徑”是怎樣構成的,是借助對應思想用排列組合知識破解該題的前提條件,即先對應,再排列.

4 異面直線問題

圖4

例4如圖4所示,底面是梯形的直四棱柱ABCD-A1B1C1D1的8個頂點可確定28條直線，在這些直線中,異面直線共有( )對.

A. 174 B. 180

C. 186 D. 192

點評 在用1個四面體去對應3對異面直線時,為了確保轉化是等價的,必須要先檢視題目中不能出現三點或多點共線的情況,即先檢視,再對應.

5 等差數列問題

例5已知數列{an}為等差數列,從集合A={a1,a2,…,a20}中取出3個不同的數,使這3個數成等差數列,則不同的等差數列共有( )個.

A. 90 B. 120 C. 180 D. 200

點評 由2j=i+k發現只要i+k為偶數便可確定唯一的j,進而先將集合A分成角標為奇數和角標為偶數兩類,再巧妙對應,即先分類,再對應.

6 不定方程問題

例6不定方程3x1+x2+…+x10=4 ①共有( )組非負整數解.

A. 9 B. 373 C. 495 D. 504

解析 當x1=1時,方程①變為x2+x3+…+x10=1,顯然有9組解;

當x1=0時,方程①變為x2+x3+…+x10=4,即(x2+1)+(x3+1)+…+(x10+1)=13,令xi+1=yi,則yi≥1(2≤i≤10),上式可等價化為y2+y3+…+y10=13. ②

綜上所述，方程①的非負整數解共有504組. 選D.

點評 通過在xi(2≤i≤10)上加上1實現了非負整數解到正整數解的轉化,再用“隔板法”進行巧妙對應從而找到問題解決的突破口,即先轉化,再對應.

7 條件傳球問題

例7甲、乙、丙、丁、戊5個人站成一圈玩傳球游戲,每次只能傳給相鄰的兩個人,從甲開始傳,若第10次球又傳回到甲的手里,則共有( )種不同的傳球方式.

A. 252 B. 254

C. 512 D. 1 024

解析 不妨設逆時針傳一次球為“+”,順時針傳一次球為“-”，則分兩種情況:

1)逆時針傳兩圈或順時針傳兩圈均可傳回到甲手中,有2種可能;

綜上所述，總的傳球方式有254種. 選B.

點評 處理該題很容易忽視對情況1)的討論,傳球次數是奇數還是偶數,是否是5的倍數等都制約著不同的對應方式,即先討論,再對應.

8 有序數組問題

例8已知A={1,2,3,…,14,15},B={a1,a2,a3},則同時滿足:①BA;②a2-a1≥3;a3-a2≥4的集合B有( )個.

A. 30 B. 56

C. 120 D. 364

點評 該題難度比較大,可以應用我們所熟知的“隔板法”來求解,但不如上述先插空,再排序,然后對應的解法，上述解法獨辟蹊徑,解題過程令人耳目一新,即先插空,再對應.

9 可重組合問題

例9從集合A={1,2,3,…,n}中取出r個數組成一組(a1,a2,…,ar),若滿足:① 數字允許重復出現;② 不計數字的順序,則稱(a1,a2,…,ar)為集合A的一個“r可重組合”,這樣的“r可重組合”共有( )個.

點評 解該題的難點是用0,1,2,…,r-1逐個加到ai(1≤i≤r)上進行鋪墊,進而實現了從“可重組合”到“無重復組合”的一一對應,然后再從集合B中選取r個元素就可順利解答該題,即先對應,再選取.

10 圍棋比賽問題

例10甲、乙兩個圍棋隊各5名隊員按事先排好的順序進行擂臺賽,雙方1號隊員先賽,負者被淘汰,然后負方的2號隊員再與對方的獲勝隊員比賽,負者又被淘汰,一直這樣進行下去,直到有一方隊員全被淘汰時,另一方獲勝,形成了一種比賽過程,那么所有可能出現的過程共有( )種.

A. 252 B. 126 C. 70 D. 35

點評 解本題的常規思路是按照比賽分5,6,7,8,9局進行討論,但先利用排列建立模型,再用對應思想進行轉化達到了增加思維量、減少計算量的目的,即先建模,再對應.

對應作為一種數學思想和方法，對處理較難的排列組合問題有著十分廣泛的應用.用該方法解題的關鍵在于構造對應關系,但此法沒有通法可尋,只有平時勤于積累,善于總結,才能依據具體問題的特征進行分析，進而合理對應,最終使問題順利獲解.