分圆问题：一个诡异的数列规律

超、凢脫俗 2023-08-17 15:46 137阅读 0赞

## 问题 ##

在圆上任取$n$个点，将每对点用直线连接起来，并规定任意三条线不能交于同一点，这些直线会将圆分割成多少份？

首先我们列出简单情况来寻找规律：

*  2个点将圆分成2份
 *  3个点将圆分成4份
 *  4个点将圆分成8份
 *  5个点将圆分成16份

![1365470-20190128120529635-852495608.png][]

看来这个数列的规律非常明显：每增加一个点，分割的份数都将乘2。然而，当点数增加到6个的时候，分割的份数不是我们预料的32，而是31。

![1365470-20190128120940693-1076669520.png][]

为了找到这个数列的通项公式，我们使用**欧拉示性数公式**（Euler’s Characteristic Formula）来进行推导：

$$V-E+F=2$$

这个公式的意思是，在任何联通平面简单图中，顶点数减边数加上面数等于2。

为了利用这个公式得到分割的份数（即为面数），我们需要先求出顶点和边的数量。

首先求顶点数：圆内的每个交点都对应圆上的4个点交叉相连，因此圆内的交点共有$C\_n^4$个，加上圆上的$n$个点，因此$V=n+C\_n^4$。

再求边数：圆内的那个交点的度数（度数是与点相连的边的个数）为4，圆上的点都与除此之外的每个点相连，因此度数是$n-1$，所以总度数为$4\*C\_n^4+n\*(n-1)$，由于每条边对于总度数的贡献为2，再加上连接圆上顶点的弦的数目，最后得边的数量$E=2\*C\_n^4+C\_n^2+n$。

![1365470-20190128122939661-1392672430.png][]

将结果带入欧拉公式，并考虑园外区域也算一个面，则分割的份数为：

$$\\begin\{aligned\}  
F-1 &= E-V+2-1 \\\\  
&= (2\*C\_n^4+C\_n^2+n)-(n+C\_n^4)+1 \\\\  
&= C\_n^4+C\_n^2+1  
\\end\{aligned\}$$

由排列组合公式，上式可以继续分解：

$$C\_n^4+C\_n^2+1 = C\_\{n-1\}^4+C\_\{n-1\}^3+C\_\{n-1\}^2+C\_\{n-1\}^1+C\_\{n-1\}^0$$

这也就解释了当$n<6$时结果总是成2的幂。

参考链接：

*  [Vedio][]
 *  [Blog][]

转载于:https://www.cnblogs.com/lfri/p/10329711.html

[1365470-20190128120529635-852495608.png]: /images/20230810/186d6fcfaa98464488eafcfe5820fb6e.png
[1365470-20190128120940693-1076669520.png]: /images/20230810/7003b1f84c8a4b64ab06135cfc8e88e9.png
[1365470-20190128122939661-1392672430.png]: /images/20230810/6599f03c198f4028a9e4267ca7b5049e.png
[Vedio]: https://www.bilibili.com/video/av19849697
[Blog]: https://silencial.github.io/2018/08/14/%E5%88%86%E5%9C%86%E9%97%AE%E9%A2%98/