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

问题:

在圆上任取 \(n\) 个点,将每对点用直线连接,并规定三条线不能交于一点,这些直线会将圆分割成多少份?


首先我们列出一些简单情况来寻找规律:

  • \(2\) 个点将圆分为 \(2\)
  • \(3\) 个点将圆分为 \(4\)
  • \(4\) 个点将圆分为 \(8\)
  • \(5\) 个点将圆分为 \(16\)

Simple Cases

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

Pattern Fail at 6

为了找到这个数列的通项公式,我们使用欧拉示性数公式(Euler's Characteristic Formula)来进行推导: \[ \displaylines{V-E+F=2 } \] 这个公式的意思是,在任何连通平面简单图中,顶点数减去边数加上面数总是等于 \(2\)

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

首先求顶点数:圆内的每个交点都对应圆上的四个点交叉相连,因此圆内的交点共有 \(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\)

Find the Correct Pattern

将结果代入到欧拉公式,并考虑到圆外区域算为一个面,则分割的份数为: \[ \displaylines{\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} } \] 由排列组合公式,上式可以继续分解: \[ \displaylines{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\) 的幂次。


参考:

  1. Video
  2. Euler Characteristic