Catalan数

Published: by Creative Commons Licence

  • Tags:

Catalan数

假设我们有n个1和m个-1,我们希望排列这n+m个数,并且要求排列$a_i$满足下面条件:

  • 对于任意$0 \leq j \leq n+m$,都有$\sum_{i\leq j} a_i \geq -k$。

我们希望求出有多少种不同的排列满足条件。

首先如果$m > n+k$,那么有效排列数一定为0。下面仅考虑$m\leq n+k$的情况。

我们知道总共的排列数为$n+m \choose n$,因此只要减去不满足条件的排列数,就可以得到满足的排列数了。下面我们考虑怎么计算不满足条件的排列数。

对于某个不满足条件的排列$B$,一定能找到最小的下标,一定能找到最小的下标j,使得,使得$\sum_{i\leq j} a_i = -(k+1)$。我们将排列。我们将排列B的从第的从第$j+1$个下标开始的值全部取相反值,即改为,改为。这样我们就得到了一个个下标开始的值全部取相反值,即$1$改为$-1$,$-1$改为$1$。这样我们就得到了一个$m-1-k$个和个$1$和$n+1+k$个的排列。要还原,我们只需要找到最小的下标个-1的排列。要还原,我们只需要找到最小的下标j,使得,使得$\sum_{i\leq j} a_i = -(k+1)$,将后面的元素取反就好了。这似乎暗示了,将后面的元素取反就好了。这似乎暗示了n个和个1和m个的无效排列与个$-1$的无效排列与$m-1-k$个和个$1$和$n+1+k$个的排列之间存在类似双射的关系。首先很明显从前者到后者一定是单射,即不同的输入对应不同的输出,同时由于个$-1$的排列之间存在类似双射的关系。首先很明显从前者到后者一定是单射,即不同的输入对应不同的输出,同时由于$m-1-k$个和个$1$和$n+1+k$个的排列中必定能找到这样的个$-1$的排列中必定能找到这样的$j$,使得前$j$个数的和为$-(k+1)$,因此映射是满射。

满射意味着$n$个$1$和$m$个$-1$的无效排列与$m-1-k$个1和$n+1+k$个-1的排列数目相同,即总有效排列数为:

\[{n+m\choose n} -{n + m \choose n + 1 + k}\]

问题1:用$n$个左括号和$n$个右括号能组成多少有效的括号序列。

首先一个括号序列有效,当且仅当排列中所有前缀部分中,左括号数不少于右括号数。如果我们将左括号视作1,右括号视为-1,取$k=0$,那么就转换为Catalan数问题了。有效数为

\[{2n\choose n} - {2n \choose n + 1}\]

问题2:给定一个$n\dot n$的网格,我们从$(0,0)$出发。假如我们现在位于$(i,j)$,且$i<n$,那么我们下一步可以到达$(i+1,j-1),(i+1,j),(i+1,j+1)$。问最后停止在$(n,k)$的总方案数有多少,这里$l\leq k\leq r$。其中$n\leq 10^5$,结果模上某个素数$p$

这个问题利用了catalan数的一个特性,设$m$为向上走的次数和向下走的次数的总和,记$x$表示向上走的次数,那么$x$一定符合:$l\leq x-(m-x)\leq r$,即$\lceil\frac{m+l}{2}\rceil\leq x\leq \lfloor\frac{m+r}{2}\rfloor$。可以发现:

\[\sum_{x=\lceil\frac{m+l}{2}\rceil}^{\lfloor\frac{m+r}{2}\rfloor}[{m\choose x}-{m\choose x+1}]={m\choose \lceil\frac{m+l}{2}\rceil}-{m\choose \lfloor\frac{m+r}{2}\rfloor+1}\]

而我们只需要枚举$m$即可得到所有的可能:

\[\sum_{m=0}^n[{m\choose \lceil\frac{m+l}{2}\rceil}-{m\choose \lfloor\frac{m+r}{2}\rfloor+1}]{n\choose m}\]

上面的公式可以$O(n)$计算。

提供一道CF类似的题目(但是是毒瘤题,需要使用扩展卢卡斯定理求组合数)。