Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
    
related: mathoverflow.net/questions/38267/… –  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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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}$ –  Milo Chen 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 –  Milo Chen 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.