查看“︁算兩次”︁的源代码

{{unreferenced|time=2014-03-26T11:47:46+00:00}}
{{Expand|time=2013-03-03T03:23:39+00:00 }}
在[[數學]]中，'''算兩次'''是一個常用的[[數學證明#常見的證明技巧|證明技巧]]，常在證明[[恆等式]]時被提到。其思想是，對一個具體的量用方法甲來計算，得到的答案是A，而用方法乙則得到B，那麼等式A = B成立。此思想雖然明顯，但在實際使用時由於方法甲與方法乙通常有明顯的差異，因此能把兩個表面上相去甚遠的式子聯繫起來。算兩次產生過很多[[漂亮的證明]]。

==組合恆等式==

[[组合數學]]中的算兩次是一种[[组合证明]]方法。我們可以對同一個[[組合計數問題]]從兩個不同的方面去觀察，從而得到兩個表達式，其值卻相同。例如以下問題：

'''設 ''n'' 為給定的正整數。假如你要創造一種語言，其中的字母只有 ※ 和 ◎ 兩種，而每個詞語總是由 ''n'' 個字母組成，那最多可以有多少個不同的詞語？'''

甲：由於詞語中任一位置都可以自由地選擇※或◎中的任何一個，所以答案是 2 &times; 2 &times; ... &times; 2 = 2<sup>''n''</sup>。

乙：如果進一步規定◎正好出現 ''k'' 次，那麼符合要求的單詞就只有 ''n 取 k'' 那麼多個了。但''k'' 可以是 0, 1, 2, ..., ''n'' 的任何一個，因此總計起來即為 <math>\sum_{k=0}^n {n \choose k}</math> ，其中 <math>{n \choose k}</math> 是[[組合數]]（n取k）。 

兩種方法都得到了'''正確'''的表達式，因此<math>\sum_{k=0}^n {n \choose k} = 2^n</math>。

==更多例子==
除了以上的[[二項式系數]]和，以下這些基本的組合恆等式也可以用算兩次的辦法來論證（但對不同的讀者來說不一定是最簡單的辦法）：

*<math>{n \choose k} = {n \choose n-k}</math>

*<math>{n+1 \choose k} = {n \choose k-1} + {n \choose k} </math>

*<math>\sum_{k=1}^n k {n \choose k} = n 2^{n-1} </math>

*<math>\sum_{k=0}^n {a \choose k}{b \choose n-k} = {a+b \choose n} </math>（來自[[超幾何分布]]的等式）

*<math>\sum_{0\leq m_i \leq n; m_1 + m_2 + ... + m_r = n} \frac{n!}{m_1!m_2!...m_r!} = r^n </math>（[[多項式系數]]和）

==富比尼定理==
[[微積分]]中的[[富比尼定理]]指出[[重積分]]在一定條件下可以用不同方法來計算。在這個意義下，算兩次也造就了不少[[分析恆等式]]。

==參見==
*證明組合恆等式的其他[[組合技巧]]，如：
**[[母函數]]
**[[遞歸關係]]

[[Category:组合数学]]
[[Category:數學推理]]