计数公式

求和

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

平方和

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

立方和

$$\sum_{i=1}^n i^3 = \left[\frac{n(1+n)}{2} \right]^2$$

排列

$$P(n,m)=\frac{n!}{m!}$$

含m个非重复元素 第i个重复元素数目为ti

$$P=\frac{P(n,m)}{\prod_{i=1}^m ti!}$$

环全排列

$$\frac{n!}{n}$$

组合

$$C_n^m=\frac{n!}{m!(n-m)!}$$
$$C_n^m=C_n^{n-m}$$
$$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$$
$$\sum_{i=0}^n C_n^i = 2^n$$

杨辉三角

1
2
3
4
5
    1
1 2 1
1 3 3 1
1 4 6 4 1
......

二项式定理

$$(a+b)^n=\sum_{k=0}^n C_n^k a^\left(n-k\right) b^k$$

lucas定理

$C_n^m \mod p = C_{n/p}^{m/p}C_{m \mod p}^{n \mod p}$

当组合数较大且取模(mod 为素数)时
普通的递推和逆元不再适用,此时可以用lucas定理

1
2
3
4
5
LL lucas(LL n,LL m)
{
if(m == 0) return 1;
return C[n%mod][m%mod]*lucas(n/mod,m/mod)%mod;
}

容斥原理

$$|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C|$$
设n个集合a1..an |ai| 表示集合元素个数
$$|a_1 \cup a_2 \cup a_3…\cup a_n|=|a_1|+|a_2|+|a_3|+…+|a_n|-|a_1 \cap a_2|-|a_1 \cap a_3|-|a_{n-1} \cap a_n|$$
$+…(+ || -)|a_1 \cap a_2 \cap a_3…\cap a_n|+(奇数个集合并集) -(偶数个集合并集)$

Fibonacci

$$F_n=F_{n-1}+F_{n-2} \,\,\,\, (n \ge 2 \, , \, F_0=F_1=1)$$
$$ f(n)=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}$$

1 1 2 3 5 8 13 21 34 55 89 …

应用

WIKI

Catalan

$$C_{n+1}=C_0C_n+C_1C_{n-1}+…+C_nC_0 \,\, \Rightarrow \,\, C_{n+1}= \sum_{i=0}^n C_iC_{n-i} \,\, (n \ge 0 \, , \,C_0=1)$$
$$C_{n}=\frac{4n-2}{n+1}C_{n-1}$$
$$C_n=\frac{(2n)!}{(n+1)!n!} = \frac{1}{n+1}(^{2n}_n)$$

1 1 2 5 14 42 132 429 1430 4862 16796 …
//从0开始

  • 所有的奇卡特兰数$C_n$都满足$n=2^k-1$,其余数都是偶卡特兰数。
    p.s. 用公式时注意先乘后除。

应用

WIKI
HDU2.3各种卡特兰

Stirling

第一类

每n个不同元素分成k组(每组中至少有一个元素),组内再按特定顺序围圈的分组方法的数目

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

第二类

n个不同元素分成k组(每组中至少有一个元素)

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

分组数

将n个相同元素分成k组(每组中至少有一个元素)

$M_(n,k) = M(n-k,k) + M(n-1,k-1)$
$M(n,1) = M(n,n) = 1$

Bell

$B_n$表示指数为n的集合的划分方法数

$B_n = \sum_{k=0}^nC_n^kB_k$
$B_0 = 1$

$B_n = \sum_{k=1}^n S(n,k)$

错位排列

我们定义$A_k$为长为n的序列中包含一个不动点的序列数。
$$
\begin{align}
&|A_p| = (n-1)! \\
&|A_p \cap A_q| = (n-2)! \\
&…
\end{align}
$$
根据容斥原理,最后的错排公式即
$$D_n = n! - C_n^1 (n-1)! + C_n^2 (n-2)! - … \pm C_n^n (n-n)!$$
化简得
$$D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+ … \pm \frac{1}{n!}) \approx \frac{n!}{e} = (n-1)(D_{n-2} + D_{n-1})$$

$D_0 = 1,D_1 = 0$

0 1 2 9 44 …

生成函数

生成函数是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息.

普通型生成函数

用于求解组合问题

对于序列$a_0,a_1,…,a_n$,他的生成函数为$f(x) = a_0 + a_1x + a_2x^2 + … a_nx^n$

如用面值为1,2,5的货币可以组成的面值,x的指数就是对应的面值,系数就是数量
$(1 + x^1 + x^2 + … )(1 + x^2 + x^4 + …)(1 + x^5 + x^10 + …)$

指数型生成函数

用于求解排列问题

对于序列$a_0,a_1,…,a_n$,他的生成函数为$f(x) = a_0 + a_1x/1! + a_2x^2/2! + … a_nx^n/n!$

用法与普通型类似

计数方法

隔板法

n 个球放进 k 个盒子(不允许有空盒子)

相当于在n-1个空中放置k-1个隔板
答案为$C_{n-1}^{k-1}$
问题等价于$x_1 + x_2 + … + x_k = n$ 的正整数解个数

n 个球放进 k 个盒子(允许有空盒子)

相当于在n+k-1个空中放置k-1个隔板
答案为$C_{n+k-1}^{k-1}$
问题等价于$x_1 + x_2 + … + x_k = n$ 的非负整数解个数

求$x_1 + x_2 + … + x_k \le n$

等价于求 $x_1 + x_2 + … + x_k + unused = n$
答案为$C_{n+k}^{k}$

题目

01串

有n个1,m个0,求保证每个位置1的累加值大于等于0的累加值
$$C_{n+m}^n-C_{n+m}^{n+1}$$
特殊地,n=m时,(Catalan数)
$$C_{2n}^n-C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n+1}$$

  • 所有情况-非法情况
  • 推导待续…

这是一个经典模型(Catalan)

  • m为左括号,n为右括号,合法方案数
    ((()))()()(()())
  • mxn的格点从(0,0)到(m,n)的不穿过对角线的路径数(只可以向上或者向右)路径数(对结果x2)

分蛋糕

小学奥数题…

直线平面划分

$$1 + \frac{n(n+1)}{2}$$

2,4,7,11,16…

折线平面划分

$$2n^2-n+1$$
hdu2050

三角形平面划分

$$3n(n-1)+2$$

直线空间划分

$$1 + \frac{n^3+5n}{6}$$

分蛋糕问题的一般公式

分蛋糕问题,只需根据前几项待定系数求解。

  • 二维:
    $$an^2+bn+c$$
  • 三维:
    $$an^3+bn^2+cn+d$$

盒放球模型

boxes&balls

连通图计数

这里默认带标号的连通图

n个点的连通图

$g_n = 2^{(^n_2)}$ 为n个点的图的数量

p.s. n*(n-1)/2 条边的选择情况

$$f_n = g_n - \sum_{i = 1}^{n-1} (^{n-1}_{i-1})f_ig_{n-i}$$

左边n个点,右边m个点的连通二分图

$$f(i,j) = 2^{ij} - \sum_{\substack{1 \leq a \leq i \\ 0 \leq b \leq j \\ a < i \vee b < j}} \begin{pmatrix}i -1 \\ a-1 \end{pmatrix}\begin{pmatrix}j \\ b\end{pmatrix} 2^{(i-a)(j-b)}f(a,b)$$