组合数学 combinatorics

组合数学比较广泛 我们这里讨论 枚举组合学.

组合数学有3个基本原理:

• 加法原理(Addition)

• 乘法原理(Multiplication)

• 容斥原理(Inclusion-exclusion)

基本研究问题

枚举组合学围绕着几个经典的问题

1. 排列组合: 排列数 P(n,k) = \frac{n!}{(n-k)!}, 组合数 \binom{n}{k} = \frac{n!}{k! (n-k)!}

2. 多重集排列: \frac{n!}{n_{1}! n_{2}! ... n_{k!}

3. 整数分拆: 将n写成正整数之和的方式数p(n)

4. 集合分拆: 第二类Stirling数 S(n,k)

5. Catalan数: \(C_n = \frac{1}{n+1} \binom{2n}{n}\) 这个和出栈顺序 二叉树 括号序列有关

6. 图计数: 标号图等