组合数学全家桶

组合数学全家桶

鸽巢原理

鸽巢原理，其实就是小学奥数里的抽屉原理。

• 把 n + 1 n+1 n+1 个元素划分至 n n n 个集合中，至少存在某个集合，其包含元素个数值大于等于 2 2 2。
• 把 m n + 1 mn+1 mn+1 个元素划分至 n n n 个集合中，至少存在某个集合，其包含元素个数值大于等于 m + 1 m+1 m+1。
• 把 n n n 个元素划分至 k k k 个集合中，至少存在某个集合，其包含元素个数值大于等于 ⌊ n k ⌋ lfloor dfrac{n}{k}rfloor ⌊kn​⌋。
• 把 q 1 + q 2 + ⋯ + q n − n + 1 q_1+q_2+cdots+q_n-n+1 q1​+q2​+⋯+qn​−n+1 个元素划分至 n n n 个集合中，至少存在某个集合 A i A_i Ai​，其包含元素个数值大于等于 q i q_i qi​。

排列组合

• 前置知识：加法原理、乘法原理

  区别：加法原理是“分步完成”，乘法原理是“分类完成”。

区别：排列与元素的顺序有关，组合与顺序无关。

排列

线排列

• 定义

  一般地，从 n n n 个不同的元素中，取出 m ( m ≤ n ) m(mleq n) m(m≤n)个元素按照一定的顺序排成一列，叫做从 n n n 个不同的元素中取出 m m m 个元素的一个线排列。

  从 n n n 个不同的元素中取出 m ( m ≤ n ) m(mleq n) m(m≤n)个元素的所有线排列的个数，叫做从 n n n 个不同元素中取出 m m m 个元素的排列数，用符号 P ( n , m ) P(n,m) P(n,m) 或 P n m P_n^m Pnm​ 表示。

• 排列数公式

  P n m = n ( n − 1 ) ( n − 2 ) ⋯ ( n − m + 1 ) = n ! ( n − m ) ! P_n^m=n(n-1)(n-2)cdots(n-m+1)=dfrac{n!}{(n-m)!} Pnm​=n(n−1)(n−2)⋯(n−m+1)=(n−m)!n!​

相异元素可重复排列

从 n n n 个不同元素中可以重复地选取出 m m m 个元素的排列，叫做相异元素可重复排列。

排列方案数： n m n^m nm。

圆排列

从 n n n 个不同元素中选取出 m m m 个元素，不分首尾地排成一个圆圈的排列叫做圆排列。

排列方案数： P n m = n ! m ( n − m ) ! P^m_n=dfrac{n!}{m(n-m)!} Pnm​=m(n−m)!n!​；如果 m = n m=n m=n， P n m ( n − 1 ) ! P_n^m(n-1)! Pnm​(n−1)!

组合

从 n n n 个数选 m m m 个，表示为 C ( n , m ) C(n,m) C(n,m) 或 C n m C_n^m Cnm​ 或 ( n m ) binom{n}{m} (mn​)。
C n m = A n m m ! = n ! m ! ( n − m ) ! C_n^m=dfrac{A_n^m}{m!}=frac{n!}{m!(n-m)!} Cnm​=m!Anm​​=m!(n−m)!n!​

二项式相关

二项式定理

( a + b ) n = ∑ k = 0 n C n k a n − 1 b k (a+b)^n=sumlimits_{k=0}^nC^k_na^{n-1}b^k (a+b)n=k=0∑n​Cnk​an−1bk

卡特兰数

卡特兰数，又称卡塔兰数（Catalan Number），是组合数学中一个常用的数列。其前几项为： 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ⋯ 1,2,5,14,42,132,429,1430,4862,cdots 1,2,5,14,42,132,429,1430,4862,⋯

关于这个数列，显然我们是找不出什么规律的，所以直接公示如下：

• 递归公式 1 1 1：
  f ( n ) = ∑ i = 0 n − 1 f ( i ) × f ( n − i − 1 ) f(n)=sum_{i=0}^{n-1}f(i)times f(n-i-1) f(n)=i=0∑n−1​f(i)×f(n−i−1)

• 递归公式 2 2 2：
  f ( n ) = f ( n − 1 ) × ( 4 × n − 2 ) n + 1 f(n)=dfrac{f(n-1)times(4times n-2)}{n+1} f(n)=n+1f(n−1)×(4×n−2)​

• 组合公式 1 1 1：
  f ( n ) = C 2 n n n + 1 f(n)=dfrac{C_{2n}^n}{n+1} f(n)=n+1C2nn​​

• 组合公式 2 2 2：
  f ( n ) = C 2 n n − C 2 n n − 1 f(n)=C_{2n}^n-C_{2n}^{n-1} f(n)=C2nn​−C2nn−1​