您的位置: 首页  >  IT文章  >  [学习笔记][组合数学]卡特兰数的一个组合意义

[学习笔记][组合数学]卡特兰数的一个组合意义

分类: IT文章 • 2024-01-04 09:07:18

引入

  • 卡特兰数 (Cat_n) 的定义为 (n) 个 (1) 和 (n) 个 (-1) 构成的，任意前缀和不小于 (0) 的序列个数

  • 众所周知卡特兰数有通项公式：

  • [Cat_n=frac{inom{2n}n}{n+1} ]

  • 可以通过容斥来推导（在任意 (n) 个 (1) 和 (n) 个 (-1) 构成的序列中，找到第一个小于 (0) 的前缀和设其位置为 (i) ，将序列 ([1,i]) 内的数全部取反）

  • 不过这里讲一种比较巧妙的组合意义

前置定理

  • 对于一个 (n) 个 (1) 和 (n) 个 (-1) 构成的序列 (s) ，存在一个 (0le i<2n) 使得 (s_{i+1dots 2n}+s_{1dots i}) （即 (i) 次循环位移之后）的任意前缀和不小于 (0)

  • 证明：将 (i) 定为 (s) 最小前缀和的位置，分 ([i+1,2n]) 和 ([1,i]) 两类讨论可以得出任意前缀和不小于 (0)

组合意义

  • 下面为了方便，假设所有 (n) 个 (1) 都是不一样的，所有 (n) 个 (-1) 也都是不一样的（即 (n) 个 (1) 和 (n) 个 (-1) 组成的数组，所有 (n!) 种重排的方案中有多少种满足任意前缀和不为负），最后除以 ((n!)^2) 即可，设所有的 (1) 标号从 (1) 到 (n) ，所有的 (-1) 标号从 (n+1) 到 (2n)

  • 考虑在末尾再加一个标号为 (2n+1) 的 (-1) ，组成一个环

  • 考虑如何从环上删掉一个 (-1) ，构成一个合法的卡特兰序列

  • 相当于以任意位置破环为链形成一个长度为 (2n+1) 的序列之后，选取一个 (1le ile 2n+1) 使得 (s_{i+1dots 2n+1}+s_{1dots i}) 的任意前缀和（最后一个位置除外）不为负

  • 类似于前置定理中提到的内容，我们可以找到一个 (i) 使得 (s) 前 (i) 个数的和最小（有多个则取 (i) 最小者），易得取这个 (i) 是唯一合法的

  • 故一个环存在唯一的删掉一个 (-1) 的方法使其变成合法的序列

  • 而我们需要保证删掉 (-1) 之后剩下的数标号必须从 (1) 到 (2n) ，也就是这个唯一的 (-1) 标号必须为 (2n+1)

  • 故所有的 (2n+1) 个元素的环中，平均 (n+1) 个环中就有一个合法的环

  • 于是我们得出：

  • [Cat_n=frac{(2n)!}{(n+1)(n!)^2}=frac{inom{2n}n}{n+1} ]

拓展

  • 卡特兰数的容斥推导和上面介绍的推导各有不同的拓展空间，下面的题目是这个组合意义的一个拓展

清华集训2016 你的生命已如风中残烛

题意

  • 有 (m=sum_{i=1}^nw_i) 个数，前 (n) 个中第 (i) 个为 (w_i-1) ，剩下的 (m-n) 个数都是 (-1)

  • 求对这 (m) 个数 (m!) 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负

  • (nle 40,1le w_ile 10^5)

做法

  • 和上面卡特兰数的组合意义推导一样，在序列的最后放上一个标号为 (m+1) 的 (-1) ，组成一个环

  • 易得对于一个环，删掉一个 (-1) 构成合法序列的方案是唯一的

  • 于是我们的要求就变成了限制这个唯一的 (-1) 的标号必须为 (m+1)

  • 而这个环上 (-1) 的个数为 (m-n+1)

  • 故答案为 (frac{m!}{m-n+1})

代码

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

const int rqy = 998244353;

int n, m, ans = 1;

int main()
{
	int x;
	read(n);
	for (int i = 1; i <= n; i++) read(x), m += x;
	for (int i = 1; i <= m; i++)
		if (i != m - n + 1) ans = 1ll * ans * i % rqy;
	return std::cout << ans << std::endl, 0;
}

相关推荐