==重複組合的概念==
=重複組合的定義=
=定義
假定n類相異物中每類均有k個以上,從這n類相異物中選取k個的組合稱為「重複組合」,方法數記為H^{n}_{k}。
=例子1
某甲到飲料店購買5杯飲料,該店售有3種飲料。於是某甲有H^{3}_{5}種購買方法。
[分析]
相異物=飲料:3\Rightarrow n = 3。
選取個數=購買杯數:5\Rightarrow k = 5。
方法數:H^{n}_{k} = H^{3}_{5}。
=重複組合與不定方程式非負整數解的關係=
=名詞定義
不定方程式:一條方程式中有2種以上(含)的未知數。
例:x + 3y = 2,這是一條方程式,但未知數有x, y共2種,所以是不定方程式。
例:3x - 5 = 4,這是一條方程式,但未知數僅有x共1種,所以不是不定方程式。
非負:若x \ge 0,則稱x為非負。
非負整數:不為負數的整數,只能是0, 1, 2, 3, \cdots。
不定方程式的非負整數解:考慮不定方程式a_1x_1 + a_2x_2 + \cdots + a_nx_n = k,其中n為自然數,k為非負整數,若c_1, c_2, \cdots, c_n皆為非負整數,且x_1 = c_1, x_2 = c_2, \cdots, x_n = c_n滿足不定方程式,則稱(c_1, c_2, \cdots, c_n)為不定方程式的一組非負整數解。
=關係
已知有n類相異物,設為S_1, S_2, \cdots, S_n,已知每類均含有k個以上的內容物,現在一共要選取k個,可以假定從S_1中選取x_1個、從S_2中選取x_2個、...、從S_n中選取x_n個,此處x_1, x_2, \cdots, x_n都必須是非負整數,於是得到(不定)方程式
x_1 + x_2 + \cdots + x_n = k.
顯然此不定方程式的每一組非負整數解都代表著一種重複組合的選取法。換言之,不定方程式的非負整數解與重複組合的選取法之間是一一對應的。只要我們可以確定所有非負整數解個數,那就表示我們可以算出所有重複組合的選取法。
=例子2
延續例子1的情境,此時有方程式
x_1 + x_2 + x_3 = 5.
寫出幾個非負整數解如下:
(5, 0, 0), (0, 5, 0), (0, 0, 5), (4, 1, 0), (1, 1, 3), (2, 2, 1).
一個技巧是然後考慮○○○○○與||(隔板)的排列,可以發現
(5, 0, 0)對應○○○○○||,
(0, 5, 0)對應|○○○○○|,
(0, 0, 5)對應||○○○○○,
(4, 1, 0)對應○○○○|○|,
(1, 1, 3)對應○|○|○○○,
(2, 2, 1)對應○○|○○|○,
可以發現每一組非負整數解對應於○○○○○與||的一種排列,所以可以判定不定方程式x_1 + x_2 + x_3 = 5一共有\frac{(5 + 2)!}{5! 2!}組非負整數解。
=定理
(i) 設n為自然數,k為非負整數,則不定方程式x_1 + x_2 + \cdots + x_n = k有\frac{(n + k - 1)!}{(n - 1)! k!}個非負整數解。
(ii) H^{n}_{k} = {{n + k - 1} \choose k}。
[證] 仿例子2作法,對不定方程式x_1 + x_2 + \cdots + x_n = k考慮k個○與n - 1個|的排列數即可。
(證明終了)
=例子3
某甲到飲料店購買5杯飲料,該店售有3種飲料。於是某甲有H^{3}_{5} = {{3 + 5 - 1} \choose 5} = {7 \choose 5} = 21種購買方法。
==用重複組合H解排列問題==
這是一個較為少見的技巧。
=問題1=
一列火車從第一車到第十車共有十節車廂,回答下列問題:
(i) 指定其中三節車廂准許吸煙,則共有多少種方法?
(ii) 若更要求此三節車廂兩兩不相銜接,則共有多少種方法?
=解法=
(i) 直接從10節車箱中任意選取3節即可,因此共有{10 \choose 3}種方法。
(ii) 假定選取的車廂的編號分別為a, b, c,再假定a號車之前有x_1個車廂、a號車與b號車之間有x_2個車廂、b號車與c號車之間有x_3個車廂、c號車之後有x_4個車廂,於是得方程式
x_1 + x_2 + x_3 + x_4 = 7,
由於要求兩兩不相銜接,因此方程式其中x_2 \ge 1, x_3 \ge 1,故可重新改寫方程式為
x_1 + x_2' + x_3' + x_4 = 5,
其中x_1, x_2'. x_3', x_4皆為非負整數。於是由前文討論知一共有H^{4}_{5} = {{4 + 5 - 1} \choose 5} = {8 \choose 3}組非負整數解,從而一共有{8 \choose 3}種方法。
(解答終了)
=問題2=
從1到20的自然數中取出三個不同的數,則三數成等差的取法有多少種?
=傳統解法=
(摘自《徐氏數學》)
先選此等差數列中最大與最小兩個(需同為奇數或同為偶數,否則等差中項不為整數),則中間項隨之確定,共有{10 \choose 2} + {10 \choose 2} = 90種方法。
(評論:學生必須熟悉等差中項的概念才可能知道一開始頭尾兩數的奇偶性必須相同,要求高了些。)
=重複組合/方程式解法=
假定選取的三數為a, b, c,再假定a前面有x_1個數、a與b之間有x_2個數、b與c之間有x_3個數、c後面有x_4個數,所以得到方程式
x_1 + x_2 + x_3 + x_4 = 17,
其中x_1, x_2, x_3, x_4皆為非負整數,由於a, b, c成等差,因此x_2 = x_3才可使得a與b距離等於b與c距離。因此方程式又可改寫為
x_1 + 2x_2 + x_4 = 17.
討論不定方程式的一個基本原則是「從係數大的變數開始」,所以從x_2開始著手。
當x_2 = 8時,x_1 + x_4 = 1,有H^{2}_{1}組非負整數解;
當x_2 = 7時,x_1 + x_4 = 3,有H^{2}_{3}組非負整數解;
當x_2 = 6時,x_1 + x_4 = 5,有H^{2}_{5}組非負整數解;
...
當x_2 = 1時,x_1 + x_4 = 15,有H^{2}_{15}組非負整數解;
當x_2 = 0時,x_1 + x_4 = 17,有H^{2}_{17}組非負整數解。
於是所求為
\begin{align*} H^{2}_{1} + H^{2}_{3} + H^{2}_{5} + \cdots + H^{2}_{15} + H^{2}_{17} &= {2 \choose 1} + {4 \choose 3} + {6 \choose 5} + \cdots + {16 \choose 15}+ {18 \choose 17} \\ &= 2 + 4 + 6 + \cdots + 16 + 18 \\ &= \frac{(2 + 18) \times 9}{2} = 90. \end{align*}
(解答終了)
=討論=
儘管用重複組合/方程式的解法乍看比較複雜,但我個人覺得這思路比較自然,同時可處理更多項數的情況,如將題目改為「從1到20的自然數中取出四個不同的數,則四數成等差的取法有多少種?」這時就沒有等差中項那種巧妙的解法。
=練習問題=
自來水公司計畫在下週一至週日之間的7天中選擇2天停止供水,若要求停水的2天不相連,則自來水公司共有多少種選擇方式?
[91,指考,數乙]
答:15。