组合数学入门 Day2

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

第一章 如何组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,但绝对误差可能会很大。

上一篇:Python IDE 详细攻略,拿去吧你~


下一篇:损失函数:交叉熵