浅谈空间分割问题
考虑这样一个问题：
$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。
接下来我们可以就可以将递推式推广至任意 $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)$。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
