對應原理（The Principle of Correspondence）

對應原理（The Principle of Correspondence）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

對應原理

已知每班教室裡有 $$36$$ 張座位。現在老師進教室後，眼光一掃，發現沒有空位，每個位子上都作了一個人。請問有多少學生？這個問題有什麼好問的，答案就是 $$36$$。但是仔細一想，老師並沒有一個一個數學生不是嗎？怎麼知道就是 $$36$$ 個？當然原因是這樣：沒有空位，每個位子上都坐一個人，表示學生和座位一樣多。

這其實就是對應原理：

對應原理：如果兩集合 $$S,T$$ 之間有一個對應(bijection)，則 $$|S| = |T|$$

再看仔細一點：老師想要知道學生的個數 $$|S|$$，但是已知座位的個數 $$|T|$$。現在學生 $$(S)$$ 和座位 $$(T)$$ 之間有一一對應(沒有空位，每個位子上都坐一個人)，因此學生和座位必須一樣多 $$(|S| = |T|)$$。

對應原理說來簡單，但是要找到好的對應來幫助解題，就是各憑本事了，這也是精彩所在。現行高中課本的排列組合並不強調對應。但是在介紹重複組合時，實際上已經偷用了對應原理。重複組合的第一個例子是：$$3$$ 種不同的水果數量皆不虞匱乏，一共要選 $$5$$ 個，共有幾種方法？這樣想：有五個水果和兩個隔板排成一列；第一個隔板之前，兩個隔板之間，第二個隔板之後分別代表三種水果的個數。多畫幾個例子：

$$\bigcirc\bigcirc\big|\bigcirc\bigcirc\big|\bigcirc$$ 表示 $$2 + 2 + 1$$，即蘋果 $$2$$ 個, 橘子 $$2$$ 個, 香蕉 $$1$$ 個.
$$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\big|\big|$$ 表示 $$5+0+0$$，即蘋果 $$5$$ 個, 橘子 $$0$$ 個, 香蕉 $$0$$ 個.
$$\bigcirc\bigcirc\bigcirc\big|\bigcirc\big|\bigcirc$$ 表示 $$3+1+1$$，即蘋果 $$3$$ 個, 橘子 $$1$$ 個, 香蕉 $$1$$ 個.
$$\big|\bigcirc\big|\bigcirc\bigcirc\bigcirc\bigcirc$$ 表示 $$0+1+4$$，即蘋果 $$0$$ 個, 橘子 $$1$$ 個, 香蕉 $$4$$ 個.
. . . . . .

因此，任何一個o, o, o, o, o, |, | 的排列就對應到一種選水果的方法。而五個球和兩根棍子的排列我們已經會算了，因此一共有 $$\frac{7!}{5!2!}=21$$ 種方法。如果不用對應原理轉化成直線排列處理，會變得非常難解釋。

尋找對應

利用 $$S, T$$ 間的對應與已知的 $$|T|$$ 來求 $$|S|$$ 是對應原理的一個面向。另一個面向可以這樣說：如果 $$|S|=|T|$$，則理論上 $$S$$ 和 $$T$$ 之間應該有個對應。

在高等數學的研究上，常常我們經過很複雜的方法，對正在研究的對象算出一個意外簡單的答案，而這個簡單的答案是我們熟知的某個結構的量；或是兩個貌似不相干的計數問題，算出同一個答案。不管是哪一種，這就表示應該有一個簡單的解釋。

例如：在上一篇文章中，我們用乘法原理得到由 $$0, 1$$ 組成的長度為 $$n$$ 的字(words) 共有 $$2^n$$ 個。另一方面，令 $${S}={x_1,x_2,\mbox{…},x_n}$$ 則其部分集合一共也有 $$2^n$$ 個。所以這兩者之間應該有一個對應關係。用 $$n=3$$ 來當例子就可以看出對應：

$$\begin{array}{rcl} \varnothing & \longleftrightarrow & 000\\ \{x_3\}& \longleftrightarrow & 001\\\{x_1,x_2\}& \longleftrightarrow & 110\\ \{x_2,x_3\}& \longleftrightarrow & 011\end{array}$$

. . . . . .

“應該有一個簡單自然的對應” 這個不起眼的一句話，是非常多的困難組合學問題以及理論發展的根源。有些尋找對應的問題已經困擾了組合學家非常久。尋找對應的背後的哲學意義是，我們希望“看穿” 一個結構，或是我們希望看穿兩個結構之間的關係。只有在找到了好的對應後，才能真正說有了真正的理解。

最後給一個簡單的有趣練習，有興趣的同學可以從這個問題體會對應原理的奧妙，也可以由此出發當作探索的專題：

1. 將 $${n}$$ 寫成一些正整數的和，次序要計(即 $$3 + 2$$ 和 $$2 + 3$$ 是不同的)，但是每個數要 $$\geq$$，有幾種方法？
2. 將 $${n}$$ 寫成一些正整數的和，次序要計，但是每個數必須是奇數，有幾種方法？
3. 解釋上面兩者的關係！