数学记录
Qfaiser
·
·
个人记录
排列组合
排列数
问：有 n 个元素，选 m 个排列，有多少种排法。
## 组合数
问：有 $n$ 个元素，选 $m$ 个，有多少种选法。
$C(n,m)=\frac{n!}{m!(n-m)!}$。
## 可重排列
问：有 $n$ 种球，第 $i$ 中有 $a_i$ 个，求把这些球排成一排有几种排法。
$(\sum _{i=1}^n a_i)!\div a_1!\div a_2!...\div a_n!
可重集合
问：有 n 种球，每种球无限个，求选 m 个球的方案。
隔板法：在 m 个球中，插入 n-1 个隔板，两个隔板之间表示这种球选几个。
问题转化成求有 m+n-1 个空，放 n-1 个隔板的方案数，即 C(m+n-1,n-1)。
圆排列
问：n 个人站成一个圈，有多少种站法。
## 错排问题
问：有 $n$ 个人，每人坐在一个凳子上，现在让这些人站起来，重新找凳子坐下，要求每个人不能坐到原来的凳子，有多少种方案。
求解方法：第 $n$ 个人假设坐在 $i$ 号凳子上，分两种情况。
（1）若第 $i$ 个人也坐在 $n$ 号凳子上，那么剩下 $n-2$ 个人的子问题。
（2）否则，此时我们可以把 $n$ 号凳子当成 $i$ 号凳子，变成 $n-1$ 个人的子问题。
递推：$f_i=(i-1)(f_{i-1}+f_{i-2})$。
## 二项式定理
$(x+y)^n=\sum_{i=0}^nC(n,i)\cdot x^i\cdot y^{n-i}
卢卡斯定理
若 p 是质数，则有 C(n,m)\bmod p=C(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)\cdot C(n\bmod p,m\bmod p)\bmod p。
卡特兰数
定义式：h(0)=h(1)=1，h(n)=\sum_{i=0}^n[h(i)\cdot h(n-i-1)]。
一阶递推式：h(n)=\frac{4n-2}{n+1}\cdot h(n-1)。
通项公式：h(n)=\frac{C(2n,n)}{(n+1)}。
不穿过对角线的简单格路问题
问：从 (0,0) 到 (n,n)，要求任何时刻向上的次数不能超过向右的次数，求方案数。
路径数=总方案数-非法方案数。
求 (0,0) 到 (n,n) 的方案数，n 步向上，n 步向右，共 2n 步，故总方案数 C(2n,n)。
我们可以把一个不合法的方案，按照第一次跨越 y=x+1 的时间点翻折，把从 (0,0) 到 (n,n) 的路径变成从 (-1,1) 到 (n,n) 的路径，n-1 步向上，n+1 步向右，共 2n 步，故非法方案数 C(2n,n-1)
答案就是 C(2n,n)-C(2n,n-1)。
出栈序列问题
问：给定 n 个元素进栈序列，求有多少种出栈序列。
任何时刻，出栈次数不超过入栈次数，同理上述网格。
二叉树问题
问：n 个点的二叉树有多少个。