物理

数竞入门定理公式总结【组合篇】

其实这篇真的很少，毕竟初中数竞组合知识点真不多，就也传点吧，自己也能用🤓👍

马上把三篇的传送门都挂到万能帖里罢( ´∀｀)

小号的几何估计不更帖了，以后几何有缺的就是大号在帖里评论了哈( ´∀｀)

预备轮的算是结束了，要不整理点对标基础轮的？不着急不着急( ´∀｀)

【正片开始】

1. 排列数公式     $A(n,k) = \frac{n!}{(n-k)!}$     （从$n$个元素中选$k$个的排列数）

2. 组合数公式     $C(n,k) = \frac{n!}{k!(n-k)!}$     （从$n$个元素中选$k$个的组合数）

3. 组合数性质

互补性：$C(n,k) = C(n, n-k)$

递推公式：$C(n,k) + C(n,k-1) = C(n+1,k)$

4. 二项式定理     $(a+b)^n = \sum_{k=0}^n C(n,k)a^{n-k}b^k$

5. 容斥原理

两集合：$|A \cup B| = |A| + |B| - |A \cap B|$

三集合：$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

6. 抽屉原理     $n$个物品放入$m$个抽屉，若n > m，则至少有一个抽屉有至少$\left\lceil \frac{n}{m} \right\rceil$个物品。

(P.S. n > m左右加美元不知道为什么会乱码，这个格式在坛里不行，但AI伴学同样有latex，测试了一下可以。。。就只能这样了( ´∀｀))

7. 圆排列

$n$个不同元素的圆排列数：$(n-1)!$

选$k$个元素的圆排列数：$\frac{A(n,k)}{k}$

8. 重复排列与组合     - 可重复排列数：$n^k$可重复组合数：$C(n+k-1, k)$

补充与进阶！

1. 分组问题

非空分组：$n$个元素分成$m$个非空组（斯特林数）：$S(n,m) = S(n-1,m-1) + mS(n-1,m)$

均分分组：$n$个元素均分$k$组（每组$m$个）：$\frac{n!}{(m!)^k \cdot k!}$（当$n = mk$）

2. 路径计数     网格中从$(0,0)$到$(m,n)$的最短路径数：$C(m+n, n)$

3. 错位排列（全错位）     $D(n) = (n-1)(D(n-1) + D(n-2))$，且$D(1)=0, D(2)=1$

4. 卡特兰数     $C_n = \frac{1}{n+1}C(2n, n)$

布什戈门初中就这么多！？补充了一点也很少啊我真的很怀疑自己整理少了，大家看看呢

初中数竞的四个板块都大体OK了，估计我也不大想补很多，看到一点补一点罢( ´∀｀)

The end