去年清明写的,现在补个档。
基于序列的卡特兰数通项公式推导
卡特兰数可认为是一个长度为 \(2n\) 的合法栈序列之集合的势。换言之,亦即所有长度为 \(2n\) 的仅由 \(-1\) 与 \(1\) 组成的序列 \(\{a_i\}\),满足
\[\forall \ 1 < i <2n,\ S_i \geq 0; \quad S_{2n} = 0 \] 后一个条件表明这个序列中 \(-1\) 与 \(1\) 的个数相同且均为 \(n\) ,只满足这个条件的序列数量很容易算出,它是 \(\binom {2n}{n}\) 。既然如此,我们不妨容斥地讨论满足后一个条件而不满足前一个条件的序列,设它们形成一个集合 \(A\)。
我们知道,如果前一个条件不被满足,意味着:
\[\exists \ 1<i<2n,\ S_i < 0 \] 因为这个前缀和 \(S_i\) 的变化是连续的,所以我们知道 \(\exists\ i,\ S_i = -1\),不妨让第一个这样的 \(i\) 之后的数全部翻转,得到一个新的序列 \(\{b_i\}\) ,对于该序列,有:
\[T_{2n} = S_i - (S_{2n}-S_{i}) = 2S_i - S_{2n} = -2 \] 如果设所有满足总和为 \(-2\) 且仅由 \(-1\) 与 \(1\) 组成的序列构成一个集合 \(B\),那么上述变换可以形式化地表述为一个映射 \(f: A \rightarrow B\),我们易知它是良定义的,证明从略。由此立即可得,集合 \(B\) 的势是\(\binom{2n}{n-1}\) (它的约束条件和先前的\(S_{2n}=0\)是类似的)。直到这里,我们似乎都并没有得出什么令人惊讶的结论。然而最大秘密潜藏在这个映射的性质之中——\(f\) 是一一映射,意味着 \(A\) 与 \(B\) 等势。这个结论可以导出卡特兰数:
\[C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n} \] 一般来讲,这个结论在几何直观上更容易被人所接受(读者可以自己画图想想!)不过我们这里提供一种纯代数的证明方法。
-
先证明 \(f\) 是一个单射。这点是显然的:如果 \(a \neq a'\) (这里 \(a\),\(a'\) 指的都是序列),因为翻转对于单个数位是单射,所以有 \(f(a) \neq f(a')\)。
-
再证明 \(f\) 是一个满射。对于 \(B\) 中的任意序列\(b\),其总前缀和 \(T_{2n} = -2\),同样是由连续性,容易知道 \(\exists\ i,\ T_i = -1\) 。还是对于这里的第一个 \(i\),将其后的数全部翻转,得到了一个 \(S_{2n} = 0\) 的序列 \(a\) ,且 \(a \in A\) 以及 \(f(a) = b\),证毕。
在证明的过程中可以发现,证明 \(f\) 是满射的时候实际上也顺带证明了其逆映射是良定义的(因为翻转是一个良定义的映射),因此其实只消说明后一点就能完成证明。
卡特兰数的推广
拓展卡特兰数的定义可以被表述为一个类似的集合的势,该集合内的元素均是长度为 \(n+m\ (n\geq m)\) ,仅由 \(-1\) 与 \(1\) 构成的序列,且满足:
\[\forall \ 1 < i <n+m,\ S_i \geq 0; \quad S_{n+m} = n-m \] 我们如法炮制,同样容斥地考虑,只满足后一条件的序列数量容易算出是 \(\binom{n+m}{n}\),接下来考虑其中不满足前一条件的序列形成的集合 \(A\) 。同样地知道,对于这些序列:
\[\exists \ 1<i<n+m,\ S_i = -1 \] 同样地翻转得到\(\{b_i\}\),
\[T_{n+m} = S_i - (S_{n+m}-S_{i}) = 2S_i - S_{n+m} = m-n-2 \] 设所有满足总和为 \(m-n-2\) 且仅由 \(-1\) 与 \(1\) 组成的序列构成一个集合 \(B\),\(|B| = \binom{n+m}{m-1}\)。我们仍得到一个映射 \(f:A\rightarrow B\),接下来我们来说明其逆映射存在。
对于 \(B\) 中的任意序列 \(b\) ,由于 \(m-n-2 \leq -2\),因此仍有 \(\exists \ 1<i<n+m,\ T_i = -1\),对于此处的第一个 \(i\),将此后所有数翻转,便能得到一个唯一且不重复的序列 \(a\) 满足 \(S_{2n} = n-m\) 以及 \(\exists \ 1<i<n+m,\ S_i < 0\)。故而 \(a\in A\),逆映射存在。因而 \(|A| =|B|\) ,扩展卡特兰数:
\[C_{n,m} = \binom{n+m}{n} - \binom{n+m}{m-1} = \frac{(n-m+1)}{n+1}\binom{n+m}{n} \] 至此我们就讨论完了在序列意义上的卡特兰数的通项公式的计算。
标签:讨论,exists,卡特兰,满足,序列,2n,binom,若干 From: https://www.cnblogs.com/JiuPleber/p/Catalan.html