组合数学学习笔记
组合数学学习笔记
组合数学常用公式
基本公式
- 排列：
\[ A_{n}^r=\frac{n!}{(n-r)!}
\]
- 组合：
\[ C_{n}^r=\frac{n!}{r!(n-r)!} \\
\dbinom{n}{r}=\frac{n!}{r!(n-r)!}
\]
- 二项式定理：
\[ n\in \mathbb{N},(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^ky^{n-k}
\]
- 广义二项式定理：
若
\[ \left | x \right |<1,\alpha\in\mathbb{R}
\]
则
\[ (1+x)^\alpha=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}x^k
\]
这里 $ \dbinom{\alpha}{k}:= \frac{\alpha^{\underline{k}}}{k!}$ 。当 \(\left | x \right |\ge 1\) 时，右侧幂级数不一定收敛。
组合公式
- 杨辉恒等式：
\[ \dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}
\]
- 等效代换：
\[ \dbinom{n}{m}=\dbinom{n}{n-m}
\]
- 连续应用1：
\[ \dbinom{n+r+1}{r}=\sum_{i=0}^{r}\dbinom{n+i}{i}
\]
- 组合意义：
\[ \dbinom{n}{m}\dbinom{m}{r}=\dbinom{n}{r}\dbinom{n-r}{m-r}
\]
- 4中 \(r=1\) 时的特例：
\[ \dbinom{n}{m}\dbinom{m}{1}=\dbinom{n}{1}\dbinom{n-1}{m-1}\\
m\dbinom{n}{m}=n\dbinom{n-1}{m-1}
\]
- 组合意义：
\[ \dbinom{n+m}{r}=\sum_{i=0}^{r}\dbinom{n}{i}\dbinom{m}{r-i}
\]
- 性质5与二项式定理：
\[ \sum_{i=0}^{n}i\dbinom{n}{i}=n2^{n-1}
\]