明天初赛

如题。来点组合数学。

Catalan & Stirling

首先是Catalan。Catalan数定义为C_n = (2n C n) / (n+1)。该数列的意义：C_n表示从(0, 0)到(n, n) 的下对角线格路径的条数。（晕乎？）换种说法，在坐标平面上，有一只蜘蛛在点(0, 0)处。它想走到(n, n)处。这只蜘蛛每次只能向右或向下移动一个单位。如果这蜘蛛从没到达直线y=x的上方（但是可以接触），那么它就有总共C_n种走法。与之等价的问题还有剧院的自动售票机等。

从Catalan数可以衍生出拟-Catalan数——C^*_n = n!C_n-1。该数的意义在《组合数学》中是以乘法格式的形式给出的，不过有点抽象。广大的OIer基本都知道合并果子，现以之为例。如果认为将第x堆与第y堆合并和将第y堆与第x堆合并是不一样的，那么将所有的果子合并为一堆的顺序就有C^*_n种。

接下来是两类Stirling数。第一类s(p, k)指将p个物体排成k个圈的方法数，由此可以证明其递归公式：s(p, k) = (p-1)s(p-1, k)+s(p-1, k-1)，方法类似于归纳法。第二类与之很相似，S(p, k)表示将p个数分成k分的方法数，递归公式：S(p, k) = kS(p-1, k)+S(p-1, k-1)。

去年就考了第二类Stirling，今年估计不会了吧。