参考教材是清华大学出版社《组合数学》第五版。

第一章 如何组CP 组合（C）与排列（P）

1.6 允许重复的组合与不相邻的集合

允许重复的集合

定义：从 \(A=\{1, 2, \cdots, n\}\) 中取 \(m\) 个元素，允许元素重复。

组合数为 \(C(n+m-1,m)\)​​ 。证明方法采用一一对应的思想。

常见应用：

线性方程 \(x_1 + x_2 + \cdots + x_n = m\) 的非负整数解的个数为 \(C(n + m - 1, m)\) 。

不相邻的集合

定义：从 \(A=\{1, 2, \cdots, n\}\) 中取 \(m\) 个元素，不存在两个相邻元素同时被取。

组合数为 \(C(n - m + 1, m)\) ，证明方法采用一一对应的思想。

1.7 组合数的一些性质

考虑组合数性质时，经常考虑”取球模型“或”网格图模型“

1. \(C(n + m, n) = C(n + m, m)\)​

2. 杨辉三角：\(C(n, m) = C(n - 1, m) + C(n - 1, m - 1)\)​ （参考网格图对角最短路径数的转移）

   • 推论：\(C(n + m + 1, m) = \sum_{k = 0}^{m}{C(n + k, k)}\)

3. \(C(n, l)\cdot C(l, r) = C(n, r)\cdot C(n - r, l - r)\)

4. \(\sum_{k=0}^n{C(n, k)} = 2^n\) （用二项式定理证明）

   • 推论：\(\sum_{k=0}^n{(-1)^k\cdot C(n, k)} = 0\)

5. \(C(n+m, r) = \sum_{k = 0}^r{C(n, k)\cdot C(m, r - k)}\)

6. \(C(n +1, m + 1) = \sum_{k = m}^n{C(k, m)}\)

1.8 Stirling 公式

\(n!\) 的近似公式。

\[n! \sim \sqrt{2n\pi}(\frac{n}{e})^n \]

\(\sim\) 表示符号两端比值的极限为 1，即相对误差随 \(n\) 趋于 \(\infty\) 而趋向 0，但绝对误差可能会很大。