排容原理(Principle of Inclusion and Exclusion)（三）

排容原理(Principle of Inclusion and Exclusion)（三）
國立高雄大學應用數學系游森棚副教授/國立高雄大學應用數學系游森棚副教授責任編輯

連結：排容原理（二）

這是一系列關於排容原理文章的第三篇。我們介紹兩個高中數學的經典問題–「Euler totient 函數 $$\phi(n)$$」與「有上界的重復組合」。

在上一篇文章中，我們證明了排容原理，然後求出錯列的個數。這篇文章中我們談兩個高中課堂教學必然面對到，但是卻一直講不清楚的問題。這兩個問題都要用到排容原理解釋，而且其實解釋非常容易。

不大於 $$n$$ 且與 $$n$$ 互質的自然數個數

幾乎所有高一學生，都曾經背過這樣的公式：設 $$n$$ 是自然數，則比 $$n$$ 小而且和 $$n$$ 互質的自然數有

$$\displaystyle n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\mbox{…}(1-\frac{1}{p_i})$$

個，其中 $$p_1,p_2,\mbox{…}p_i$$ 是 $$n$$ 的所有質因數。

比如說，$$60=2^2\cdot{3}\cdot{5}$$，所以比 $$60$$ 小而和 $$60$$ 互質的自然數有

$$60\cdot(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=16$$ 個。

為什麼能這樣算？！為什麼這樣算得出答案？！能說得出所以然的學生比例應該“非常低”，因為這個式子的證明要用到排容原理。

我們令

$$\phi(n):=$$ 比 $$n$$ 小而和 $$n$$ 互質的自然數，

這是數學上的一個重要函數，叫做 Euler’s totient function。所以學生背的公式就是 Euler’s totient function的值。上例說明 $$\phi(60)=16$$。底下我們藉由計算 $$\phi(60)$$ 來說明這公式怎麼來的。

$$60=2^2\times{3}\times{5}$$，質因數為 $$2,3,5$$。
在 $$X:=\{1,2,\mbox{…},60\}$$ 之中，令

$$A_1:= 2$$ 的倍數
$$A_2:= 3$$ 的倍數
$$A_3:= 5$$ 的倍數

我們要算那些與 $$60$$ 互質的數，亦即既非 $$2$$ 倍數，又非 $$3$$ 的倍數，又非 $$5$$ 的倍數：亦即要求

$$|~\overline{A_1}\bigcap\overline{A_2}\bigcap\overline{A_3}~|$$

由排容原理，等於

$$|X|-|A_1|-|A_2|-|A_3|+|A_1\bigcap{A_2}|+|A_1\bigcap{A_3}|+|A_2\bigcap{A_3}|-|A_1\bigcap{A_2}\bigcap{A_3}|$$

$$=\displaystyle 60-\frac{60}{2}-\frac{60}{3}-\frac{60}{5}+\frac{60}{2\cdot{3}}+\frac{60}{3\cdot{5}}-\frac{60}{2\cdot{3}\cdot{5}}$$

$$=\displaystyle 60(1-\frac{1}{2}-\frac{1}{3}-\frac{1}{5}+\frac{1}{2\cdot{3}}+\frac{1}{2\cdot{5}}+\frac{1}{3\cdot{5}}-\frac{1}{2\cdot{3}\cdot{5}})$$

$$=\displaystyle 60(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})$$

中間每一項都是顯然的，比如 $$|A_1\bigcap{A_3}|$$ 表示 $$\{1,2,\mbox{…}{60}\}$$ 之中同時是 $$2,5$$ 的倍數，當然有 $$\frac{60}{2\cdot{5}}=10$$ 個。所以，為什麼質因數會出現在分母，為什麼有減號，為什麼前面要乘上 $$n$$，為什麼公式是這樣，現在都變成非常透明了。一般來說，有以下的定理：

定理１（Euler totient function）

令 $$n={p}_1^{a_1}{p}_2^{a_2}\mbox{…}{p}_t^{a_t}$$ 為一自然數，則不大於 $$n$$ 且與 $$n$$ 互質的自然數共有

$$\displaystyle\phi(n)=n\prod^{t}_{i=1}\left(1-\frac{1}{p_i}\right)$$ 個。

有上界的重複組合

由高中數學的重複組合理論我們知道，對於非負整數 $$k$$，不定方程 $$x_1+\mbox{…}+x_n=k$$ 的非負整數解有

$$H^n_k=\dbinom{n+k-1}{k}$$ 組。

例如 $$x_1+x_2+x_3+x_4=12$$ 的非負整數解有 $$H^4_{12}=\dbinom{15}{12}$$ 組。

這相當於 $$12$$ 個一樣的球丟到 $$4$$ 個不同箱子的方法數。

如果每個變數約定下界，也是可以算的，

例如要求 $$x_1+x_2+x_3+x_4=12,x_1\geq{2},x_2\geq{1},x_3\geq{0},x_4\geq{3}$$ 的整數解，

相當於先分別給 $$x_1,x_2,x_3,x_4$$ 四個箱子 $$2,1,0,3$$ 個球。手上還剩六個球可以亂給，因此解有

$$H^4_6=\dbinom{4+6-1}{6}$$ 組。

但是高中課堂會避開“給定上界”的情況。問題是，既然有給下界的問題，當然可以問給上界的問題。但是為什麼不提？可能是坊間教材沒有提及，課堂就不教了－實際課堂的教學常常被坊間的補充資料牽著鼻子走。給定上界求非負整數解當然也是基本問題，這類問題用排容原理就可以處理。

底下我們看一個簡單的例子說明排容原理怎麼作這類問題。

假設我們要求 $$x_1+x_2+x_3=12,x_1\leq{4},x_2\leq{7},x_3\leq{3}$$ 的整數解。

在 $$X:=x_1+x_2+x_3=12$$ 的 $$H^3_{12}=\dbinom{14}{12}=91$$ 組非負整數解之中，令

$$A_1:=x_1\geq{5}$$ 的那些解。
$$A_2:=x_2\geq{8}$$ 的那些解。
$$A_3:=x_3\geq{4}$$ 的那些解。

所以我們要算

$$|\overline{A_1}\bigcap\overline{A_2}\bigcap\overline{A_3}|$$，

由排容原理，這等於

$$|X|-|A_1|-|A_2|-|A_3|+|A_1\bigcap{A_2}|+|A_1\bigcap{A_3}|+|A_2\bigcap{A_3}|-|A_1\bigcap{A_2}\bigcap{A_3}|$$

嘿，你看，接下來就好辦了－把每一項都算出來就成了，而且每一項都是“給定下界”，這個我們會算！

現在，$$|A_1|=H^3_7$$（先丟進去 $$5$$ 個球，手上還有 $$7$$ 個球）；同理 $$|A_2|={H}_4^3,|A_3|={H}_8^3$$；

而 $$|A_1\bigcap{A_2}|=0$$（否則需要至少 $$13$$ 個球），$$|A_1\bigcap{A_3}|={H}_3^3,|A_2\bigcap{A_3}|={H}_0^3$$；

最後 $$|A_1\bigcap{A_2}\bigcap{A_3}|=0$$。所以所求為

$${H}_{12}^3-{H}_7^3-{H}_4^3-{H}_8^3+0+{H}_3^3+{H}_0^3-0=6$$

這個方法是一般的，反正，給定上界，就是可以這樣算。附帶一提，類似的問題其實用生成函數（generating function）來處理，才是一勞永逸的辦法－不管條件怎麼給，生成函數可以處理所有的問題。

如同這兩個例子一樣，先把那些不要的條件列為 $$A_1,A_2,\mbox{…},A_n$$，然候確定要算的是 $$|\overline{A_1}\bigcap\overline{A_2}\bigcap\mbox{…}\bigcap\overline{A_n}|$$。排容原理的形式一旦確立了，計算都變成非常容易且機械化。讀者在此應該可以體會，為什麼在第一篇文章中，我們要特別強調排容原理的正確形式－真正的排容原理是在算 $$|\overline{A_1}\bigcap\mbox{…}\bigcap{\overline{A_n}}|$$，而非對偶的 $$|A_1\bigcup\mbox{…}\bigcup{A_n}|$$。

讀者可以牛刀小試，試試底下這個名題，稱為直線版本的Lucas夫婦問題。我相信讀者會非常訝異：排容原理的形式一旦確定後，問題變得如此容易。

問題１（Menage problem of Lucas）有 $$n$$ 對夫婦坐成一列。問夫婦不相鄰的方法數有多少種？

答案是 $$\displaystyle \sum^n_{k=0}(-2)^k\binom{n}{k}(2n-k)!\ $$ 種，讀者作對了嗎？

希望這篇文章有助於師生釐清文中所介紹的兩個問題。在下一篇文章中，我們要更進一步談排容原理的抽象形式。

連結：排容原理（四）