# 重複組合H
## 轉換成方程式解題
組合C除了一般取物情況之外，還有一種變形，這種情況被稱為**重複組合H**：
### Example 2.3.1
一飲料店販售3種飲料，而小華欲購買5杯飲料，則小華共有幾種購買方式？
:::spoiler Hint:可以用未知數以代數形式表示看看
遇到組合題目先初步簡化，假設三種飲料分別購買了 $x、y、z$ 杯，則原題目可以變成代數形式表示：
$x+y+z=5\ \ (x,y,z \in \mathbb{Z} \land x,y,z \geq 0)$
而這樣的代數形式解的數量為$H_{5}^{3}$
$H_{5}^{3}=C_{5}^{7}=21$

A:21種
:::
\
若要計算重複組合，可以先將題目轉換成代數形式用H表示更方便。
而怎麼將重複組合轉換成熟悉的組合數C表示呢？我們就要先理解這個代數方程式：
$x+y+z=5\ \ (x,y,z \in \mathbb{Z} \land x,y,z \geq 0)$
這個方程式敘述的意思為3個未知數相加是5，欲求(x,y,z)的非負整數解。
用重複組合表示這題的答案就是$H_{5}^{3}$組。

接下來就是如何將重複組合H轉換成容易計算的組合C：

先將等號後的5拆成**5個數字1**相加，而三個未知數表示有兩個加號插入這5個1之中，這兩個加號隔開了三個區域，分別為x、y、z的值。
則方程式的解就是**5個數字1**和**2個加號**的排列，共有$C_{5}^{7}$種組合。

了解了以上這個方程式，之後若遇到題型可以轉換成這樣的方程式，我們就可以用重複組合H來計算！

若m個不同的未知數相加為n，則方程式非負整數解有$H_{n}^{m}$組
同理可證，重複組合數$H_{n}^{m}=C_{n}^{m+n-1}$，其中m為未知數的數量，n為未知數相加總和值。

試試用重複組合解決以下這個例題：
### Example 2.3.2
有7顆紅球，欲將所有紅球分裝到3個不同的箱子中，也可以有箱子為空，則共有多少分配情形？
:::spoiler Hint:用重複組合H換組合C
用重複組合H解決問題
先定義三個箱子的紅球數量分別有x,y,z顆，則可以得到以下方程式：
$x+y+z=7\ \ (x,y,z \in \mathbb{Z} \land x,y,z \geq 0)$
根據定義可以知道組合數有$H_{7}^{3}=C_{7}^{9}=C_{2}^{9}=36$種

A:36種
> [!Important] 如何將重複組合H換成組合C
> 可以把方程式看作7個`1`與2個`+`的排列，則兩個加號所隔開的三個區域就分別是x,y,z的值。
> 則可以知道排列數有$C_{7}^{9}$種。
> 這樣就成功把H換成C表示並計算了
:::
\
除了一般的H計算之外，H還有一些額外的變形

## H不等式
### Example 2.3.3
試求$x+y+z \leq 5$的非負整數解$(x,y,z)$有幾組？
:::spoiler Hint:遇到H不等式，就創造垃圾桶
先創造一個垃圾桶$\alpha$後將原式改寫：
$x+y+z+\alpha=5$的非負整數解$(x,y,z,\alpha)$
而$\alpha$的數值不重要，因為剩下的x,y,z組合都可以保證不重複且不超過5
則可以知道$(x,y,z,\alpha)$的組數有$H_{5}^{4}=C_{5}^{8}=C_{3}^{8}=56$種

A:56種
:::
\
如果遇到H不等式，根據其目要求可以靈活改變垃圾筒的擺放位置，有時候可以非常間單的解決題目！

## 有值域的H
有些時候不是每次的未知數都要求非負整數解，如果有限制值域的未知數，還是可以轉換成H來計算。
### Example 2.3.4
媽媽要將8份相同點心分配給4個小孩，但希望每個小孩都至少要有一份點心，則點心分配可以有幾種情況？
:::spoiler Hint:可以先假設每個小孩已經有一份點心，再開始分配
根據題意，可以先假設4個小孩分別拿到的點心數量有w,x,y,z個，則可以列出方程式：
$w+x+y+z=8\ \ (w,x,y,z \in \mathbb{N})$
但這樣的列式不是熟悉的重複組合，所以我們假設每個人都已經先拿一份點心了，則可以改寫原方程式：
$(w'+1)+(x'+1)+(y'+1)+(z'+1)=8\ \ (w',x',y',z' \in \mathbb{Z} \land w',x',y',z' \geq 0)$
整理後得：
$w'+x'+y'+z'=4\ \ (w',x',y',z' \in \mathbb{Z} \land w',x',y',z' \geq 0)$
這樣就將題目轉換成熟悉的H了，則點心的分配情況數有$H_{4}^{4}=C_{4}^{7}=C_{3}^{7}=35$種

A;35種
:::

靈活運用這些重複組合的技巧，可以在面對組合數時有更直覺的H可以使用。雖然看似神奇又複雜的重複組合，但實際理解後有時甚至能速解很多題型！

# 有趣例題講解
### Problem 2.3.1
小明預定在陽台上種植玫瑰、百合、菊花和向日葵等四種盆栽。如果陽台上的空間最多能種8盆，可以不必擺滿，並且每種花至少一盆，則小燦買盆栽的方法共有幾種？(104學測數學)
:::spoiler :relieved: Hint:轉換H方程式+建立垃圾桶+有值域的H
先假設四種花各有w,x,y,z盆，但因為最多只能種8盆，又每種花又至少要一盆，先寫出原題方程式：
$w+x+y+z \leq 8\ \ (w,x,y,z \in \mathbb{N}$
要求不等式的H就建立一個垃圾桶$\alpha$，裡面數值不重要；而有值域的未知數表示每個花都先種了一盆，則方程式又可以改寫成：
$(w'+1)+(x'+1)+(y'+1)+(z'+1)+\alpha=8\ \ (w',x',y',z',\alpha \in \mathbb{Z} \land w',x',y',z',\alpha \geq 0)$
整理後得：
$w'+x'+y'+z'+\alpha=4\ \ (w',x',y',z',\alpha \in \mathbb{Z} \land w',x',y',z',\alpha \geq 0)$
根據上述方程式，可以得出解的數量有$H_{4}^{5}=C_{4}^{8}=70$種

A:70種
:::

### Problem 2.3.2
方程式$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}+x_{9}+x_{10}=3$的非負整數解有幾組？

:::spoiler :relieved: Hint:先單獨分析x1再用H
分析x1的值發現x1只可能為0或1，則分兩種case計算：
(1) if $x_{1}=0$
則$x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}+x_{9}+x_{10}=3$
的非負整數解有$H_{3}^{9}=C_{3}^{11}=165$組
(1) if $x_{1}=1$
則$x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}+x_{8}+x_{9}+x_{10}=1$
的非負整數解有$H_{1}^{9}=C_{1}^{9}=9$組
綜合上述可知所有非負整數解共有165+9=174組

A:174組
:::

### Problem 2.3.3
試從下列選項中，選出答案為$C_{n}^{n+3}$的選項。
(1) $x_{1}+x_{2}+x_{3}+x_{4}=n$的非負整數解數對$(x_{1},x_{2},x_{3},x_{4})$數量
(2) 從4種不同皮包中共挑選出n個皮包的方法數
(3) 將n本相同的書發給4個小朋友的方法數
(4) 從n+3個相異物中取出3個的方法數
(5) 若n>3，則$C_{0}^{2}+C_{1}^{3}+C_{2}^{4}+...+C_{n}^{n+2}$
:::spoiler :cold_sweat: Hint:組合數化簡+H重複組合
(1)完全的H方程式表示，直接根據H的定義得非負整數對有$H_{n}^{4}=C_{n}^{n+3}$種
(2)先令這四種皮包分別拿了$x_{1},x_{2},x_{3},x_{4}$個，則可以列出方程式與(1)完全一樣，得方法數有$H_{n}^{4}=C_{n}^{n+3}$種
(3)一樣令4位小朋友分別有$x_{1},x_{2},x_{3},x_{4}$本書，則可以列出方程式與(1)完全一樣，得方法數也有$H_{n}^{4}=C_{n}^{n+3}$種
(4)取物直接用C來寫，方法數有$C_{3}^{n+3}=C_{n}^{n+3}$種
(5)根據$C_{b}^{a}+C_{b}^{a}=C_{b+1}^{a+1}$化簡組合數，先把$C_{0}^{2}$換成$C_{0}^{3}$，則原式可以化簡:
$\begin{split}C_{0}^{2}+C_{1}^{3}+C_{2}^{4}+...+C_{n}^{n+2}&=(C_{0}^{3}+C_{1}^{3})+C_{2}^{4}+...+C_{n}^{n+2}\\&=(C_{1}^{4}+C_{2}^{4})+...+C_{n}^{n+2}\\&=C_{2}^{5}+...+C_{n}^{n+2}=...=C_{n}^{n+3}\end{split}$

A:(1)(2)(3)(4)(5)
:::