Catalan数

Published: December 20, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• Catalan数

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\cdot 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类似的题目（但是是毒瘤题，需要使用扩展卢卡斯定理求组合数）。