经典组合问题

在此记录一些经典的组合问题,方便日后查阅。

卡特兰数,斯特林数,放球问题

卡特兰(Catalan )数

$n$ 个0和 $n$个1 组成的序列中始终要保持任意前缀中0的个多不超过1的个数的序列个数为 $\frac{1}{n+1} {2n \choose n }$

这个问题跟括号合理性等一系列问题合理性有关。

$n$ 个0 和 $m$ 个 1 组成的序列($n \leq m$) 保持 任意前缀中 0 的个数不超过1的个数的序列个数为:

把0当$x$-轴,1当$y$-轴,不合理的情况必然经过 $y = x+1$, 在第一次不合理时,后面的路径就开始与 $y = x +1$ 对称,最终结束点为 $(n-1, m+1)$

斯特林(Stirling)数

关于这个问题可以参考这篇博客

第一类斯特林数等到以后用到了再写吧

第二类斯特林数: 将$n$个不同的元素拆分成$m$ 个非空集合的方案数$S(n,m)$。显然有递推关系式:

又我们知道:

将 $n$ 个任意的放在$m$ 个不同盒子中。右边的枚举非空盒子数量$i$,$i$ 个盒子因为是不同的所以要乘$i!$ (不用担心算多了,因为一旦分配好了,盒子本身即使无区别,放了东西就有区别了)

从我的这篇博文 直接可知 (把$n$ 看作常数):

改写成大家通常见到的形式也就是:

正整数分拆数

将正整数$n$拆分成$m$个非负整数之和的方案数$f(n,m)$:

$n$ 个球放在$m$个盒子中

球有相同和不同两种情况,盒子也是,还有盒子能空和不能空,一共八种情况:

  • 球同,盒同,非空

    正整数拆分数之和 $f(n,m) - f(n,m-1) $

  • 球同,盒同,能空

    正整数拆分数$f(n,m)$

  • 球同,盒异,非空

    等价于 $x_1 + \cdots + x_m = n $ 的正整数解,插空法知道$n-1 \choose m-1$

  • 球同,盒异,能空

    同上,$n+m-1 \choose m-1 $

  • 球异,盒同,非空

    第二类斯特林数: $S(n,m)$

  • 球异,盒同,能空

    同上, $\sum_{i=1} ^m S(n,i)$

  • 球异,盒异,非空: $m!S(n,m)$

  • 球异,盒异,能空: $m^n$

欧尼酱,人家想喝可乐!