几个恒等式的组合证明.PDFVIP

幾個恆等式的組合證明 許介彥 私立大葉大學 電機工程學系 壹、前言 數學上有相當多恆等式可以利用組 從集合 0,1,2,, n 中選出不同的兩 合的方式來證明；當我們要證明某個式子 數，總共有多少種選法？這是一個相當容 的等號左右兩邊相等，我們就「發明」一 易的問題，既然集合中有 n 1個不同的 個與計算數量有關的問題，說明等號兩邊 數，答案當然是C(n 1,2) ，也就是 同樣都是該問題的答案（只是想法不同而 n 1 已）；既然答案只有一個，所以等式成立。   ( 1)  2  n n2 各類恆等式中，與二項式係數   所有這些選法可依所選出的兩數中較大的 （binomial coefficients ）有關的恆等式特 數是多少分為 n 類；有些選法中較大的數 別容易透過組合的方式來證明，因為 為 1 ，有些為2 ，…… ，有些為n ；如果我 C(n, k ) 可視為從 n 個東西中選出 k 個的方 們能夠知道這 n 類的每一類各有幾種選 法數，數的本身就含有組合上的意義。本 法，這些選法數的總和應該就等於 文假設當n k 時，C(n, k ) 的值為 0 。 C(n 1, 2) 。 讓我們再看個例子。下面是與二項式 考慮兩數中較大的數為 k （ ） 係數有關的一個基本的式子： 1k n 的情形，此時另一個數有可能是多少呢？ n n             由於另一數須小於k ，因此有0, 1, 2, , k 1 k n k     等總共 k 個可能的值。如前所述，當 我們「發明」的計數問題是：從 n 個人中 k 1, 2, , n ，所有選法數的總和等於 選出 k 個人的方法有幾種？答案顯然是 C(n 1, 2) ，因此下式一定成立： C(n, k ) ，不過由於選出k 個人其實也相當 n n n  於將n k 個人排除，而由 n 人中選出n k ( 1) k 2 人來排除的方法有C(n, n k ) 種，因此上式 k 1 這就是我們熟悉的由 1 開始的連續正 成立。 整數求和公式，此式在數學上有很多種證