MENU

浅谈空间分割问题

考虑这样一个问题:

$n$ 个 $k-1$ 维超平面最多能将一个 $k$ 维空间分割为多少个部分?

我们熟知的是 $k=2$ 时的情况,即用 $n$ 条直线去分割一个平面最多能将平面分为多少部分,答案为 $\dfrac{n(n+1)}{2}+1$​(A000124),问题在拓展后实际上变得很有意思,所以记一下自己的一些想法。

记拓展问题的答案为 $D_{k,n}$。

我们先不急着考虑一般化的情况,首先试着让 $k=3$。

经过艰难的手玩过程,我们至少可以解决答案序列的前几项:
$$
D_3=\{1,2,4,8,15,26,\dots\}
$$
没有头绪的话,我们对其进行差分:
$$
\Delta D_3=\{1,2,3,4,13,\dots\}
$$
这个时候,你会发现这玩意恰好就是 $D_2$,也就是说,我们有递推式:
$$
D_{3,n}=D_{3,n-1}+D_{2,n-1}
$$
也就容易得到 $D_{3,n}=\dfrac{n^3 + 5n + 6}6$(A000125,Cake numbers)。

那么,如何理解这个递推式呢?

递推式启发我们去考虑「向三维空间中添加一个平面」这一过程的本质。我们知道添加一个平面对答案产生的贡献与 $D_2$ 有很大关联,这启发我们将视线放在新添加的这个二维平面上。

事实上,原先的 $n-1$ 个平面交在新平面上形成了 $n-1$ 条直线,将新平面分为了若干区域,这每个区域恰好对应了新平面对原来三维空间中一个部分的分割,也就是将一个部分分成了两半,也就对答案作出了 $1$ 的贡献。

再回过头去看递推式的话,意义也就十分清晰了。

此时,我们还可以以一个更高的眼光去审视 $k=2$ 的情况,如果希望求出添加一条直线所产生的增量,我们只需考虑点分割直线的情况即可。

OEIS 上也提供了对以上数列的解释以及推广,不失为一种很好的参考。

Update:这篇 blog 写完后,惊奇的发现 matrix67 也对这个问题有过细致的思考,并且讨论了平面分割环面的问题,其中对于二维以及三维情况提供了非常直观的插图 /bx。

matrix67's blog

接下来我们可以就可以将递推式推广至任意 $k\in \mathbb{N}$,这里同时也给出较为形式化的表述。

假设 $k$ 维空间中已经存在了 $n-1$ 个 $k-1$ 维超平面,并且将空间分割为了 $D_{k,n-1}$ 个部分,现在添加一个新的超平面 $\alpha$,我们希望最大化 $D_{k,n-1}\to D_{k,n}$ 的增量 $\Delta$。

原有的 $n-1$ 个超平面与 $\alpha$ 的「交」在 $\alpha$ 上形成了 $n-1$ 个 $k-2$ 维的子空间,并将 $\alpha$ 分割成了 $t$ 个区域,$\alpha$ 上的每个区域恰好对应了 $\alpha$ 对原空间中一个部分的分割,i.e. $\Delta=t$,于是我们有 $\Delta_\max=t_\max=D_{k-1,n-1}$。

可以写出递推式:
$$
D_{k,n}=D_{k,n-1}+D_{k-1,n-1}
$$
用递推式计算 $D_{k,n}$ 的复杂度是 $O(nk)$ 的。

通项的求法,我们考虑使用生成函数。

设 $G_k(x)$ 为 $D_k$ 的生成函数,我们有 $G_1(x)=\dfrac{1}{(1-x)^2}$。

递推式用生成函数描述就是:
$$
G_k(x)=\dfrac{x}{1-x}G_{k-1}(x)+\dfrac{1}{1-x}
$$
如果我们将 $G_1(x)$ 表示为 $\dfrac{x}{(1-x)^2}+\dfrac{1}{1-x}$,那么不难得到:
$$
G_k(x)=\sum_{i=1}^{k+1}\dfrac{x^{i-1}}{(1-x)^i}
$$
于是有:
$$
\begin{aligned}
D_{k,n}&=[x^n]G_k(x)\\
&=\sum_{i=1}^{k+1}[x^n]\dfrac{x^{i-1}}{(1-x)^i}\\
&=\sum_{i=1}^{k+1}[x^{n-i+1}]\dfrac{1}{(1-x)^i}\\
&=\sum_{i=0}^{k}\binom{n}{i}
\end{aligned}
$$
至此,复杂度降至 $O(k)$。

Last Modified: October 26, 2022
Archives Tip
QR Code for this page
Tipping QR Code