组合数

组合数求和公式

公式： $$ \sum_{k=0}^n \binom{n}{k} = 2^n $$

解释：

二项式定理：根据二项式展开式，令 $x = 1$： $(1 + 1)^n = \sum_{k=0}^n \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^n \binom{n}{k}.$ 因此，和为 $2^n$。
组合意义：从 $n$ 个元素中选取任意多个元素（包括选 0 个或全选），总共有 $2^n$ 种方式。

示例：

当 $n = 3$ 时： $\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3} = 1 + 3 + 3 + 1 = 8 = 2^3.$

公式： $$ \sum_{k=0}^n k \binom{n}{k} = n \cdot 2^{n-1} $$

解释：

代数推导：利用二项式定理的导数： $\frac{d}{dx} \left( (1+x)^n \right) = n(1+x)^{n-1} = \sum_{k=0}^n k \binom{n}{k} x^{k-1}.$ 两边乘以 $x$，再令 $x = 1$，得： $\sum_{k=0}^n k \binom{n}{k} = n \cdot 2^{n-1}.$
组合意义：从 $n$ 人中选一个委员会（任意大小），再选一个主席。总共有两种方式：
1. 先选主席（$n$ 种选择），再从剩余 $n-1$ 人中任意选成员（$2^{n-1}$ 种）。
2. 先选 $k$ 人（$\binom{n}{k}$ 种），再从 $k$ 人中选主席（$k$ 种），总数为 $ \sum_{k=0}^n k \binom{n}{k}$。

示例：

当 $n = 4$ 时： $0\binom{4}{0} + 1\binom{4}{1} + 2\binom{4}{2} + 3\binom{4}{3} + 4\binom{4}{4} = 0 + 4 + 12 + 12 + 4 = 32 = 4 \cdot 2^{3}.$

公式: $$ \sum_{k=1}^{\lceil (n-1)/2 \rceil} \binom{n}{2k+1} = \sum_{k=0}^{\lceil (n-1)/2 \rceil} \binom{n}{2k} = 2^{n-1} $$

由二项式展开可证

平方和公式： $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.$ 解释：从 $2n$ 个元素中选 $n$ 个，等价于分成两组各 $n$ 个，并选 $k$ 个从第一组、$n−k$ 个从第二组。
交替符号和： $\sum_{k=0}^n (-1)^k \binom{n}{k} = 0 \quad (n \geq 1).$ 解释：由二项式定理 $(1 - 1)^n = 0$。

这些公式在概率论、组合优化和算法分析中有广泛应用，例如动态规划中的状态转移计数。