问题:

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


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

  • $2$ 个点将圆分为 $2$ 份
  • $3$ 个点将圆分为 $4$ 份
  • $4$ 个点将圆分为 $8$ 份
  • $5$ 个点将圆分为 $16$ 份

Simple Cases
Simple Cases

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

Pattern Fail at 6
Pattern Fail at 6

为了找到这个数列的通项公式,我们使用欧拉示性数公式(Euler’s Characteristic Formula)来进行推导:

$$ V-E+F=2 $$

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

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

首先求顶点数:圆内的每个交点都对应圆上的四个点交叉相连,因此圆内的交点共有 $C^n_4$ 个,加上圆上的 $n$ 个点,因此 $V=n+C^n_4$ 。

再求边数:圆内的每个交点的度数为 $4$ ,度数是与点相连的边的个数,圆上的每个点都与除此之外的点相连,因此度数为 $n-1$ ,所以总度数为 $4C^n_4+n(n-1)$ , 由于每条边对于总度数的贡献为 $2$ ,再加上连接圆上顶点的弦的数量,最后得到边的数量 $E=2C^n_4+C^n_2+n$ 。

Find the Correct Pattern
Find the Correct Pattern

将结果代入到欧拉公式,并考虑到圆外区域算为一个面,则分割的份数为:

$$ \begin{equation*} \begin{split} F-1 &= E-V+2-1 \\ &= (2C^n_4+C^n_2+n)-(n+C^n_4)+1 \\ &= C^n_4+C^n_2+1 \end{split} \end{equation*} $$

由排列组合公式,上式可以继续分解:

$$ 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