##### 组合 - 组合 - **组合**是从 $n$ 个元素的[[集合]]中, 不计顺序地抽出 $k$ 个对象, 形成一个[[子集]]的过程, 组合与子集概念等价, 组合数是所有组合结果的数量, 可用[[阶乘]]定义, 记为 $C_n^k$ 或 $\binom{n}{k}$ . 例如从 $\{a,b,c\}$ 中取出两个元素进行组合, 可能的结果有 $\{a, b\}$, $\{a, c\}$, $\{b, c\}$. 如果允许元素重复, 则为[[多重集组合]]. 如果每次抽出后放回, 则为[[重复组合]]. 可推出[[二项式定理]], 组合数与二项式系数等价 - $\displaystyle C_n^k=\frac{n!}{(n-k)!k!}$ >[!example]- 组合数 >- $\displaystyle C_n^k=\frac{n!}{(n-k)!k!}$ > - 首先从另一个角度考虑[[排列|排列数]] > - 第 $1$ 步, 从 $n$ 个对象中取出 $k$ 个, 有 $C_n^k$ 种选法 > - 第 $2$ 步, 将 $k$ 个对象做全排列, 有 $P_k^k$ 中排法 > - $P_n^k=C_n^kP_k^k$ > - $\displaystyle C_n^k=\frac{P_n^k}{P_k^k}=\frac{n!}{(n-k)!k!}$ > - $C_n^k=C_n^{n-k}$ > - $C_n^{k+1}+C_n^k=C_{n+1}^{k+1}$ > - $\displaystyle C_5^3=\frac{5\cdot4\cdot3}{3\cdot2\cdot1}=10$ >[!example]- 恒等式 >- 阶乘展开式 > - $\displaystyle \binom{n}{k} = \frac{n!}{(n-k)!k!}$ >- 对称恒等式 > - $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ >- 递推恒等式 > - $\displaystyle\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ > - $\displaystyle\binom{n}{0} = 1$, $\displaystyle\binom{0}{k} = 0$ >- 二项式定理 > - $\displaystyle (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$ >- 范德蒙德卷积 > - $\displaystyle \sum_{k=0}^r \binom{m}{k} \binom{n}{r - k} = \binom{m + n}{r}$ >- 平方和恒等式 > - $\displaystyle \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$ >- 吸收恒等式 > - $\displaystyle \binom{n}{k} = \frac{n}{k}\binom{n - 1}{k - 1}$ >- 上指标反转 > - $\displaystyle \binom{r}{k} = (-1)^k \binom{k - r - 1}{k}$ >- 上指标求和 > - $\displaystyle \sum_{m=0}^n \binom{m}{k} = \binom{n+1}{k+1}$ >- 平行求和法 > - $\displaystyle \sum_{k=0}^n \binom{r + k}{k} = \binom{r + n + 1}{n}$