从四象八卦到万象天元

线代课上思考的一个比较综合的问题，花了若干天时间研究清楚了，发表一下思考过程。

关于超空间分割

$n$ 维超空间中 $m$ 个 $n-1$ 维超平面最多能将空间分割为多少份？ 后文将其计作 $F(n,m)$。

$n=2$

两仪生四象

二维空间中，$m$ 个条直线最多将平面分成多少份？

在二维空间 ($n=2$) 中，高中组合数学告诉我们一个比较经典的观察：答案是 $1+1+2+\dots m= \binom {m+1} 2 + 1= \frac{m(m+1)}{2}+1$，它的推导来源如下：

$0$ 条直线时，平面有 $1$ 份。

$1$ 条直线时，它把这个区域割开，增加 $1$ 份。

$2$ 条直线时，它把原来两个区域都割开，增加 $2$ 份。

每个区域都被切到，被切到后增加一个区域，此时平面共 $1 + 1 + 2 = 4$ 份。（直角坐标系的四个象限）

$3$ 条直线时，它无法同时割开这四个区域，而仅能割开 $3$ 个平面，增加 $3$ 份（比如直角坐标系和一条不与坐标轴平行的直线），或者三条不交与一点的直线。

我们开始思考这个 $3$ 的来源：从无限远处，这条线开始切割平面的某个区域，当与某一条直线相交后，进入一个新的区域，并开始切割这个区域。

因为总共会与 $2$ 条直线相交，所以切割的区域发生了两次变化，所以总共切割了 $3$ 个区域，增加了 $3$ 个平面。

以此类推：第 $i$ 条直线可以和前 $i-1$ 条直线相交，切割平面上的 $i$ 个区域，增加 $i$ 个区域。

所以 $F(2,m)=1+\sum_{i=1}^{m} i=1+\frac {m(m+1)}{2}$。

这里有一个和计数关系不大的点用于证明：为什么发生变换后切割的一定是不同的区域？不会从 $1\to 2\to 1$ 这样变回去吗？因为每个区域是若干半平面的交，一定是凸多边形，不可能出现与一条直线相交在多个区域。

$n=3$

四象生八卦

三维空间中，$m$ 个二维平面能将空间分成多少份？

人类是三维生物，这仍处于具象认知范围内，我们继续用大脑思考。

第一个平面，将空间分为两部分，显然。

第二个平面，与第一个平面相交于一条直线，我们横着看过去，看到的就是一个十字形，平面投影就是 $n=m=2$ 的 case，将空间分为四部分。

第三个平面的加入与二维空间不一样了，第三个平面可以同时切割原来的四个空间，只需要同时与这两个平面相交就行了，会为空间增添四个部分，比如空间直角坐标系的八个卦限，就是三个平面将空间分为八个部分的例子，$x=+/-,y=+/-,z=+/-$，共 $2\times 2\times 2 = 8$ 种。

这个时候可能会很自然地以为四个平面的答案是 $16$ 个部分：下一个平面能不能将已有的 $8$ 个区域都切割掉，为空间增添 $8$ 个部分？答案是否定的，你无法在空间直角坐标系中作出一个平面同时切割八个卦限，最多可以与七个卦限相交，如下图中的平面 $x+y+z=1$：

它与除了 $(-,-,-)$ 的其它七个卦限全部相交，切割出七个新的空间，所以 $F(3,4)$ 的答案是 $8+7=15$。

$7$ 这个数字肯定并非凭空产生，试图思考它是如何生成的：平面能切割的空间数量与平面的什么有关？

第四个加入的平面会与前三个平面相交，交线会将平面分成若干个区域，平面的每一个区域都对应切割着一个小空间。

让我们回到第三个平面加入时来理解这件事：第三个平面加入时会与前两个平面相交，形成两条交线，将平面分成四份，而这个平面的每一份小平面都对应着切割着空间中的一小份：

试着想象这样一件事：有一个俯视图是 “田” 的四个站在一起的棱柱（两条线的分割）形状的蛋糕，直接横着对着这个蛋糕来一刀，能够多切出四块来（二阶魔方），其原因是切面是一个 ”田” 字形，四个切面上的小区域分别各自切割了一个空间。所以切面上每一个区域切割一个小空间。

我们继续加入第四个平面，它能切割的部分空间数，就是其它三个平面和它的交线将这个新平面分割出的区域数！平面上的每一块区域都切割了原本空间的某一处封闭小空间，而其它三个平面和它的交线将这个平面分割的份数，正是 $7$ ！（感叹号，不是阶乘）

第四个平面被前三个平面分割的样子，就是前面这张图！

所以说，$7$ 其实是 $F(2,3)$ 的答案！前三个平面提供的三条交线，恰好可以将这个平面分为七份！而平面的每个区域，都划分出一个新的空间！

于是加入第五个平面时，空间会增加的部分数，就是四条直线将平面分割的部分数，$F(2,4)=11$。

加入第 $m$ 个平面时，空间会增加的部分数，就是 $m-1$ 条直线将平面分割的部分数，$F(2,m-1)$。

$$ F(3,m)=F(3,m-1) + F(2,m-1) $$

累加得到

$$ F(3,m) = 1 + F(2,0) + F(2,1)+F(2,2) \dots F(2,m - 1) = 1+\sum _{i=0} ^{m-1} F(2,i) $$

带入 $F(2,m)$ 的公式，直接计算：（使用 $\sum_0^n i^3 =\frac{1}{6}n(n+1)(2n+1)$）

$$ \begin{aligned} F(3,m) &= 1+\sum_{i=0}^{m-1} \big(\frac{i(i+1)}{2}+1\big)\\ &= 1+\sum_{i=0}^{m-1} \big(0.5i ^2+0.5i+1\big)\\ &= 1+\frac{1}{2}\times \frac{1}{6} (m - 1)(m)(2m - 1)+\frac{1}{2}\times \frac{1}{2}(m-1)(m)+m\\ &= \frac{1}{6} m^3+ \frac {5}{6} m+1 \end{aligned} $$

向高纬延拓

在地观天，有限观无限。

五维和以上的空间对于没有想象过高维空间的我来说已经是抽象思维了，丢掉大脑，让我们来用小脑思考一下。

在平面数量较少时，不妨仅仅思考四维空间的一个三维切片被分割的部分数。

对于四维超空间，第一个三维超平面将超空间切割出一个新的部分（它在某个三维切片上的投影是一个二维面），现有 $2$ 部分。

第二个加入的超平面将原本的两个超空间各自分割形成一个新的部分（现在三维切片上的投影是两个相交的二维面），现有 $2+2=4$ 个部分。

第三个加入的超平面会分割原本的四个超空间，现在三维切片上的投影是一个空间直角坐标系的八个卦象，现有 $4+4 = 8$ 个部分。

接下来我们加入第四个三维超平面，它能切割超空间的多少个部分？ 类比三维空间中每个小平面切割一个空间， 第四个 3d超平面会合前三个超平面交于三个 $\text{2d}$平面，这三个 $\text{2d}$平面会将 $\text{3d}$超平面分割为 $8$ 份，每份都切割着 $ \text{4d}$ 超空间中的一个部分。为什么是八份呢？因为这个新加入的三维超平面中，它和前三个平面的交集构成了一个空间直角坐标系的八个卦限，也就是 $F(3,3) = 8$。现空间被分割为 $8+8=16$ 个部分。

第五个三维超平面呢？它会与前四个超平面相交，使得它被四个“超交线”切割（每个超交线是一个二维平面），这个超平面（三维空间）被这四个超交线（二维平面）分割成了 $F(3,4) = 15$ 个区域，每个区域继续切割。

于是我们可以累加，发现

$F(4,m)=1+F(3,0)+F(3,1)+F(3,2)+\dots +F(3,m-1)$

我们继续推广到 $n$ 维空间， $n$ 维空间中加入的第 $m$ 个 $\text{(n-1)d}$超平面切割的空间数，就是这个 $\text{(n-1)d}$超平面被它与之前 $m-1$ 个 $\text{(n-1)d}$超平面的超交线切割出的$\text{(n-1)d} $区域数，每个 $\text{(n-1)d} $区域会将$\text{nd} $超空间切割出一个新的部分！

所以 $n$ 维空间中加入的第 $m$ 个 $\text{(n-1)d}$超平面，新增了 $F(n-1,m-1)$ 个空间部分，所以有：(原来的+新增的)

$$ F(n,m)=F(n,m-1) + F(n-1,m-1) $$

回归统计

所以我们发现了一个基于相邻项的递推关系（其初始情况为 $m=0$，此时空间未被切割）：

$$ F(n,m)=F(n,m-1)+F(n-1,m-1)\\ F(n,0) = 1 $$

这个递推关系已经足以我们求出 $F(n,m)$ 的值了。接下来我们尝试求出更本质的 $F$ 的公式。

注意到 $F$ 的邻项递推的关系和二项式系数的递推关系是非常类似的

$$ \begin{aligned} F(n,m) & =F(n,m-1)+F(n-1,m-1)\\ \\ \binom m n & = \binom {m-1}{n}+\binom{m-1}{n-1} \end{aligned} $$

仅仅有初始条件不同： $F(n,0) = 1$，对于所有 $n\geq0$ 成立， 而 $\binom 0 n = 1$ 仅在 $n=0$ 时成立。

这启发我们直接从组合意义上考虑，$F(n,m)$ 和 ”在 $m$ 个不同物品中选择不超过 $n$ 个的方案数” 一一对应（完全等价）！

考虑第 $m$ 个物品是否选择，若不选，则剩下 $m-1$ 个物品，仍然选择不超过 $n$ 个；若选择，剩下 $m-1$ 个物品中需要选择不超过 $n-1$ 个！所以其递推式恰好为

$$ F(n,m) = F(n,m-1) + F(n-1,m-1) $$

而边界同为 $F(n,0) = 1$：$m=0$ 时，选择方案数总是 $1$，初值相同和递推方式相同，所以完全等价。

因为 $F(n,m)$ 和 ”在 $m$ 个不同物品中选择不超过 $n$ 个的方案数” 完全等价，我们直接考虑枚举选择了几个物品，我们又可以将这个组合定义导出为

$$ F(n,m)=\sum _{i=0}^{n} \binom {m}{i} $$

即二项式系数的行和。至此，我们获得了 $F(n,m)$ 的公式。

该公式还有一种基于数学归纳的严谨推导，但是算量略大，且和组合数学关系不大，就是纯算，在这里就不耗费篇幅列出。

特殊情况

这也解释了我们之前猜测答案为 $2^m$ 的误解，$m\leq n$ 时，确实有 $F(n,m) = 2^m$，因为 $F(n,m)=\sum _{i=0}^{n} \binom {m}{i}$，其中 $i\geq m$ 时，有 $\binom m i = 0 $，所以 $F(n,m)=\sum _{i=0}^m \binom m i= \sum _{i=0}^m \binom m i 1^{i}\times 1^{m-i}$，$\text{binomial theorem}$ 指出这个值等于 $(1+1)^m =2^m$。

这也符合我们的认知，在 $n$ 维空间 $\mathbb R^n$ 中，我们总是可以选出 $m(m\leq n)$ 个正交的超平面，所以空间中每个点都在超平面的正侧或是负侧，所有半平面交总共有 $2^m$ 中可能的正负侧的情况，所以共切割出 $2^m$ 个区域。

我们之后会在其它文章中慢慢探讨 $n<m$ 时这个公式和线性代数的关联。

Mindset

思想：类比、递归、降维、观察、联想、追究数据意义、递推的组合意义

知识：组合数学、递推、空间几何、高维空间、线性代数