特殊计数序列:

Catalan 数列

$C_n=\frac{1}{n+1}\dbinom{2n}{n}$

组合解释:

给定由 $n$ 个 $1$ 和 $n$ 个 $-1$ 构成的序列,求需满足 $\forall i\in[1,2n],\sum\limits_{j=1}^i a_j\ge 0$ 的方案数。
首先总方案就等于 两个有 $n$ 个相同元素的多重集 组合在一起的方案数,即 $\frac{2n!}{n!n!}=\dbinom{2n}{n}$

减去不合法方案数 $U$ ,

考虑第 $k$ 个位置时,首次出现 $\sum_{j=0}^k a_j<0$ ,即 $\sum_{j=0}^{k-1}a_j=0,a_k=-1$ 。

把前 $k$ 个数反转,就可以得到一个有 $n-1$ 个 $-1$ 和 $n+1$ 个 $1$ 的序列,显然这样的互逆是唯一的,

那么方案数就为 $\frac{2n!}{(n+1)(n-1)!}$

相减就得 $C_n$ 。

划分数

$f(n,m)=f(n-m,m)+f(n,m-1)$

有两种解释方法:

  1. 有 $n$ 个相同的盒子,$m$ 个相同的球必须放完的方案数
  2. 把整数 $n$ 划分,且最大数不过 $m$ 的方案数。

第一种递推的组合解释:

考虑当前是否有空盘,

无空盘:因为我们无法得知方案里哪些为空盘,不妨每一个盘都先 $+1$,方案为 $f(n-m,m)$ 。

有空盘:同样地,我们无法保证之前有无空盘,因此强制把 $m$ 作为空盘,方案为 $f(n,m-1)$ 。

易得这样计数是不重不漏的,因为情况仅分为空盘与无空盘。

第二种递推的组合解释:

类似地,考虑当前是否加入 $m$

即可得到想要的递推式。