3
$\begingroup$

Let a(n) represent the number of regions that the plane R2 is broken into by n lines (no 2 of which are parallel, and no 3 of which intersect in a single point).

Let b(n) represent the number of regions that the 3-dimensional space R3 is broken into by n planes (no 2 of which are parallel, and no 3 of which intersect in a shared line).

Find either a recursive formula or a closed-form solution for a(n) and b(n).

So I know that a(n)=C(n+1,2)+1. Why should b(n) be any different? I simply cannot visualize it.

$\endgroup$
1
$\begingroup$

$a(n)$ is known as the lazy caterer's sequence, while $b(n)$ is known as the cake number. They are different starting from $n=3$, notice placing the three "canonical planes" split space into $8$ quadrants, while $a(n)=7$

$\endgroup$
  • $\begingroup$ Thats useful! Thanks! $\endgroup$ – Blessoul Jan 28 '15 at 3:59
  • $\begingroup$ It would be useful to show why the cake number is cubic in $n$ while the lazy caterer's number is quadratic. $\endgroup$ – Ross Millikan Jan 28 '15 at 4:18
  • $\begingroup$ @RossMillikan: It took me over 4 years to come across this question, but I think my answer addresses your comment. $\endgroup$ – robjohn Sep 29 '19 at 7:27
1
$\begingroup$

$n$ points divides $\mathbb{R}^1$ into at most $\binom{n}{0}+\binom{n}{1}$ pieces.


When dividing $\mathbb{R}^2$, line $n$ meets the $n-1$ previous lines at $n-1$ points, dividing line $n$ into $\binom{n-1}{0}+\binom{n-1}{1}$ pieces. Each of those pieces of line $n$ divides a piece of $\mathbb{R}^2$ in two, adding $\binom{n-1}{0}+\binom{n-1}{1}$ pieces of $\mathbb{R}^2$. We start with $1=\binom{n}{0}$ piece of $\mathbb{R}^2$, so after adding $n$ lines, we get $$ \begin{align} a(n) &=\binom{n}{0}+\sum_{k=1}^n\left[\binom{k-1}{0}+\binom{k-1}{1}\right]\\ &=\binom{n}{0}+\binom{n}{1}+\binom{n}{2} \end{align} $$ pieces of $\mathbb{R}^2$. We used the Hockey Stick Identity to evaluate the summations above.


When dividing $\mathbb{R}^3$, plane $n$ meets the $n-1$ previous planes at $n-1$ lines, dividing plane $n$ into $\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}$ pieces. Each of those pieces of plane $n$ divides a piece of $\mathbb{R}^3$ in two, adding $\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}$ pieces of $\mathbb{R}^3$. We start with $1=\binom{n}{0}$ piece of $\mathbb{R}^3$, so after adding $n$ planes, we get $$ \begin{align} b(n) &=\binom{n}{0}+\sum_{k=1}^n\left[\binom{k-1}{0}+\binom{k-1}{1}+\binom{k-1}{2}\right]\\ &=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3} \end{align} $$ pieces of $\mathbb{R}^3$.


Thus, $b(n)-a(n)=\binom{n}{3}$.

$\endgroup$
  • $\begingroup$ Well done!.......... $\endgroup$ – Ross Millikan Sep 29 '19 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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