P5377 [THUPC2019] 鸽鸽的分割 题解

简要题意

连结圆上 \(n\) 个点，求最多能够把圆分成几个部分。

前置知识

欧拉公式：\(F(ace)=E(dge) - V(ertex)+2\)

人话：\(\text{多边形面数} = \text{边数} - \text{顶点数} + 2\)

思路

将一个圆折叠成一个多面体，你可以进行一些奇妙的空间变换来达到这一点。

那么我们最后会多出一个底面。

因此在我们的这个圆中 \(F(n)=E-V+1\)

求 \(V\)

圆上已经有了 \(n\) 个点。我们要使得圆内不存在三线共点的情况。

那么考虑每次选择四个顶点画出一个四边形的两条对角线。

于是又会生成 \(C_{n}^{4}\) 个顶点。可以证明已经考虑完全了，于是有

$$ V = n + C_{n}^{4} $$

求 \(E\)

原有 \(C_{n}^{2}\) 条边，且圆环上的 \(n\) 个点互相连接构成 \(n\) 条边。

每多一个交点会增加两条多边形边。又有 \(2\times C_{n}^{4}\) 条。

$$ E = n + C_{n}^{2} + 2\times C_{n}^{4} $$

最后，我们展开这个逆天的柿子：

$$ \begin{aligned} F(n) &= E - V + 1 \\ &= n + C_{n}^{2} + 2\times C_{n}^{4} - n - C_{n}^{4} + 1 \\ &= C_{n}^{2} + C_{n}^{4} + 1 \\ &= \dfrac{n(n - 1)}{2} + \dfrac{n(n - 1)(n - 2)(n - 3)}{4\times 3 \times 2} + 1 \\ &= \dfrac{x^4}{24} - \dfrac{x^3}{4} + \dfrac{23x^2}{24} - \dfrac{3x}{4} + 1 \end{aligned} $$

去 OEIS 上校验结果，正确。