用重複組合H解排列問題

==重複組合的概念==

=重複組合的定義=

=定義

假定$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。