NanoApe's Blog

既是咸鱼又是辣鸡

【数论】组合数学、群论

NanoApe posted @ 2016年1月05日 20:23 in 蒟蒻不撕烤智熵何来 , 449 阅读

 

排列组合

$$A(n,r) = \frac {n!}{(n-r)!}$$

$$C(n,r) = \frac {n!}{(n-r)!r!}$$

$$C(n,r) = C(n,n-r)$$

$$C(n,k) = C(n-1,k)+C(n-1,k-1)$$

$$C(n+r+1,r) = \sum_{i=0}^{r} C(n+r-i,r-i)$$

$$C(n,k)C(k,r) = C(n,r)C(n-r,k-r) \quad (k \ge r)$$

 

特殊排列组合

可重复n选r组合数:$C(n+r-1,r)$

圆周n选r排列数:$Q(n,r)=A(n,r)/r$

 

排列Hash函数

对于排列$a_1,a_2,a_3....a_n$,设

$$b_i=\sum_{k=i+1}^n [a_i>a_k]$$

$$Hash=\sum_{i=1}^n b_i*(n-i)!$$

要恢复也很简单

 

整数拆分

整数$n$拆分成一些重复次数不超过$k$的整数的拆分数,等于整数$n$拆分成不被$k+1$除尽的整数的拆分数(允许重复)

整数$n$拆分成$k$个数的拆分数,等于整数$n$拆分成最大数为$k$的拆分数

整数$n$拆分成不超过$k$个数的拆分数,等于整数$n$拆分成最大数不超过$k$的拆分数

整数$n$拆分成互不相同的若干奇数的拆分数,等于整数$n$拆分成自共轭的Ferrers图像的拆分数

整数$n$拆分成不超过$k$个数的拆分数,等于整数$n+k$拆分成恰好$k$个数的拆分数

 

Stirling数

①(n个元素分作k个环排列的方案树)

$$s(n,0)=0$$

$$s(1,1)=1$$

$$s(n+1,k)=s(n,k-1)+ns(n,k)$$

②(n个元素分作k个非空集合的方案树)

$$S(n,k)=0 ~ (n<k ~or~ k=0)$$

$$S(n,n)=S(n,1)=1$$

$$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

③(可以用此式进行FFT)

$$\begin{align} S(n,k)&=\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}C(k,j)j^n \\ &=\sum_{j=1}^{k}\frac{(-1)^{k-j}}{(k-j)!}\frac{j^n}{j!} \end{align}$$

 

Catalan数

$$h(0)=1,h(1)=1,h(n)=h(0)h(n-1)+h(1)h(n-2)+...+h(n-1)h(0) ~ (n>1)$$

$$h(n)=h(n-1)\frac {4n-2}{n+1}$$

$$h(n)=\frac {C(2n,n)}{n+1}$$

 

错排公式

$$D_n=n!(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+\frac{(-1)^n}{n!})=(n-1)(D_{n-1}+D_{n-2})$$

 

组合公式

$$\sum_{k=1}^n (2k-1)^2=\frac {n(4n^2-1)}{3}$$

$$\sum_{k=1}^n (2k-1)^3=n^2(2n^2-1)$$

$$\sum_{k=1}^n k=\frac {n(n+1)}{2}$$

$$\sum_{k=1}^n k^2=\frac {n(n+1)(2n+1)}{6}$$

$$\sum_{k=1}^n k^3=(\frac {n(n+1)}{2})^2$$

$$\sum_{k=1}^n k^4=\frac {n(n+1)(2n+1)(3n^2+3n-1)}{30}$$

$$\sum_{k=1}^n k^5=\frac {n^2(n+1)^2(2n^2+2n-1)}{12}$$

$$\sum_{k=1}^n k(k+1)=\frac {n(n+1)(n+2)}{3}$$

$$\sum_{k=1}^n k(k+1)(k+2)=\frac {n(n+1)(n+2)(n+3)}{4}$$

$$\sum_{k=1}^n k(k+1)(k+2)(k+3)=\frac {n(n+1)(n+2)(n+3)(n+4)}{5}$$

$$\sum_{k=1}^n \prod_{i=0}^{g-1} (k+i)=\frac {\prod_{i=0}^{g}(n+i)}{g+1}$$

 

Burnside引理

设$G$是一个有限群,作用在集合$X$上。对每个$g$属于$G$令$X^g$表示$X$中在$g$作用下的不动元素。

伯恩赛德引理断言轨道数(记作$|X/G|$)由如下公式给出:

$$|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|$$

说人话,就是有m个置换k种颜色,所有本质不同的染色方案数就是每种置换下的不变染色方案数的平均数。

 

Lucas定理

$$C(n,m) \equiv C(n/p,m/p)C(n\%p,m\%p) \pmod p$$

 

默慈金数

$n$ 个数,可以为 $+1,0,-1$,保证 $\sum_i^a k_i(1\le a \le n)$ 非负且所有数总和为0的方案数

$$M_{n+1}=M_n+ \sum_{i=0}^{n-1}M_i M_{n-1-i} = \frac{(2n+3)M_n+3nM_{n-1}}{n+3}$$

Avatar_small
slongle 说:
Mar 11, 2016 09:24:11 AM

错排公式是不是错了..

Avatar_small
NanoApe 说:
Mar 11, 2016 10:23:35 PM

啊貌似对啊……
查了查红书上面是这样写的啊……

Avatar_small
NanoApe 说:
Mar 11, 2016 10:29:09 PM

啊确实是错的……
查了维基改过来了
书中的东西不可信啊……
Thanks!>.<


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter