凸多边形 k 划分计数

凸多边形 k 划分计数

给定 \(n,k\)，求凸 \(n\) 边形划分成 \(k\) 个不相交部分的方案数。

sol

先引入一个定理：

Raney 定理：和为 \(1\) 的整数序列的所有循环位移序列中有且仅有一个满足任意前缀和大于 0。

证明可以考虑任取一个循环位移序列，然后求前缀和，找到最靠右的前缀和最小的位置向后一位作为起点。（实际上可以在坐标系上画出前缀和的折线图，拿斜率 \(\frac{1}{n}\) 的直线去切）

下面我们要构造双射。

我们给一个凸多边形顶点顺时针（或逆时针）编号为 \(1\) 到 \(n\)。

从 \(2\) 号点开始，维护一个栈。每遍历到一个点 \(i\)，先向栈顶塞入 \(i\)。再进行 \(t\ge 0\) 次 pop 操作，每次操作从栈顶向下的位置（也就是 \(i\) 前面）弹出正整数个点，然后把该点与栈顶向下的点连边（如果栈大小变为 1，与 1 号点连边），\(t\) 就是 \(i\) 号点向前连边的数量。

同时维护一个序列，向栈中加入元素时向序列中 push_back 一个 1；弹掉 \(p>0\) 个元素时向序列中 push_back 一个 \(-p\)。为了保证整个序列的和为 1，最后再加入一个负数，使栈中只剩一个元素。

可以发现，生成的序列的任意前缀和大于 0。且对于任意一个和为 1，前缀和大于 0，由 \(n-1\) 个 1 和 \(k\) 个负数构成的序列，我们都可以生成互不相同的多边形划分方案。所以二者构成双射。

我们只要数出由 \(n-1\) 个 1 和 \(k\) 个负数构成的和为 1 的序列数量，再根据 Raney 定理乘上系数 \(\dfrac{1}{n+k-1}\) 即可。

数量就是 \(\dfrac{1}{n+k-1}\dbinom{n+k-1}{k}\dbinom{n-3}{k-1}\)。