# How many resulting regions if we partition $\mathbb{R}^m$ with $n$ hyperplanes?

This is a generalization of this question. So in $\mathbb{R}^2$, the problem is illustrated like so:

Here, $n = 3$ lines divides $\mathbb{R}^2$ into $N_2=7$ regions. For general $n$ in the case of $\mathbb{R}^2$, the number of regions $N_2$ is $\binom{n+1}{2}+1$. But what about if we consider the case of $\mathbb{R}^m$, partitioned using $n$ hyperplanes?

Is the answer $N_m$ still $\binom{n+1}{2}+1$, or will it be a function of $m$?

-
– leonbloy Jun 2 '13 at 18:39
@Milo What's the way that you know how to prove the above theorem? You can adapt the proof accordingly. $m$ will be involved in your answer. – Calvin Lin Jun 2 '13 at 21:08

Hint: Let's consider how to prove that in $\mathbb{R}^2$, the maximum number of distinct regions is $\frac { n^2 + n + 2 } { 2}$.

First, since there are finitely many lines, we can tilt any configuration such that no line is parallel to the horizontal. Now, let's consider the 'lowest' point of any region.

If the region is bound below, than such a point must exist, is unique, and is a point of intersection of 2 lines. In fact, there is a one-to-one relation between regions that are bounded below, and these points of intersections, which gives us ${ n \choose 2 } = \frac{n^2-n} {2}$ regions.

What happens if the regions are not bounded below? How many are there? Well, let's simply insert a horizontal line way down below, and count the number of unbounded regions, by associating them to these new bounded regions. Now, let's consider the 'lowest, leftmost' point of any region. If the region is bound to the left, then such a point must exist, is unique, and is appoint of intersection of the original $n$ lines with the new horizontal line. In fact, there is a one-to-one relation between regions that are unbounded below, bounded to the left, and these points of intersections, which gives us ${n \choose 1} = n$ regions.

Finally, how many regions are not bounded below, and not bounded to the left? You should convince yourself that there is ${n \choose 0} = 1$ regions.

Hence, the total number of ways is ${n \choose 2} + {n\choose 1} + {n \choose 0}$.

Now, you can easily see how this shows that the number of regions for the hyperplane version of your problem is $$\sum_{i=0}^m {n \choose i}.$$

-
What if $n < m$? Should the general formula not be $\sum^{\min(m, n)}_{i = 0} \binom{n}{i}$ so that we have $N_m = 2^n$ ($n<m$) when there are not enough hyperplanes to finish cutting all $m$ dimensions in half, only the first $n$ of them hence $2^n = \sum^{n}_{i = 0} \binom{n}{i}$ – mchen Jun 3 '13 at 15:53
@MiloChen Note that if $a < b$, then ${ a \choose b } = 0$. Hence the formula still holds. You might need to do some work to check that the formula is still valid, and indeed it is. Basically, for those low values, the answer is just $2^n$, because each hyperplane can cut each existing region into 2 (e.g. slice along each axis-hyperplane). – Calvin Lin Jun 3 '13 at 15:56
Ahh, I didn't know the binomial coefficient had a definition of $0$ under the case $a<b$ - thanks – mchen Jun 3 '13 at 15:59
@MiloChen The binomial coefficient can be generalized to where $a$ is any real value. – Calvin Lin Jun 3 '13 at 16:01
It must pass through $\sum_{i=0}^{m} {n+1 \choose i} - { n \choose i}$, by just taking the difference of the formula above. – Calvin Lin Jun 3 '13 at 16:49