算两次

组合数学中的算两次是一种组合证明方法。我们可以对同一个组合计数问题从两个不同的方面去观察，从而得到两个表达式，其值却相同。例如以下问题：

设 n 为给定的正整数。假如你要创造一种语言，其中的字母只有 ※ 和 ◎ 两种，而每个词语总是由 n 个字母组成，那最多可以有多少个不同的词语？

甲：由于词语中任一位置都可以自由地选择※或◎中的任何一个，所以答案是 2 × 2 × ... × 2 = 2ⁿ。

乙：如果进一步规定◎正好出现 k 次，那么符合要求的单词就只有 n 取 k 那么多个了。但k 可以是 0, 1, 2, ..., n 的任何一个，因此总计起来即为 ${\displaystyle \sum _{k=0}^{n}{n \choose k}}$  ，其中 ${\displaystyle {n \choose k}}$  是组合数（n取k）。

两种方法都得到了正确的表达式，因此${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n}}$ 。

除了以上的二项式系数和，以下这些基本的组合恒等式也可以用算两次的办法来论证（但对不同的读者来说不一定是最简单的办法）：

• ${\displaystyle {n \choose k}={n \choose n-k}}$ 

• ${\displaystyle {n+1 \choose k}={n \choose k-1}+{n \choose k}}$ 

• ${\displaystyle \sum _{k=1}^{n}k{n \choose k}=n2^{n-1}}$ 

• ${\displaystyle \sum _{k=0}^{n}{a \choose k}{b \choose n-k}={a+b \choose n}}$ （来自超几何分布的等式）

• ${\displaystyle \sum _{0\leq m_{i}\leq n;m_{1}+m_{2}+...+m_{r}=n}{\frac {n!}{m_{1}!m_{2}!...m_{r}!}}=r^{n}}$ （多项式系数和）

微积分中的富比尼定理指出重积分在一定条件下可以用不同方法来计算。在这个意义下，算两次也造就了不少分析恒等式。

• 证明组合恒等式的其他组合技巧，如：
  • 母函数
  • 递归关系