# Are there publications or references describing $N$ dimensional space divided by $N-1$ dimensional (hyper)planes?

As a teenager I was given this problem which took me a few years to solve. I'd like to know if this hae ever been published. When I presented my solution I was told that it was similar to one of several he had seen.

The problem:

For an $$n$$ dimensional space, develop a formula that evaluates the maximum number of $$n$$ dimensional regions when divided by $$k$$ $$n-1$$ dimensional (hyper)planes.

Example: $$A$$ line is partitioned by points: $$1$$ point, $$2$$ line segments. $$10$$ points, $$11$$ line segments, and so one.

• @Jamie: Such type of questions cannot be answered. Just google it and see it for yourself.
– anonymous
Aug 11, 2010 at 18:23
• @Chandru1: Why cannot it be answered? Aug 11, 2010 at 18:24
• @ShreevatsaR: Common, how does one know that this has been published or not, and if he is curious in knowing it i am sure it will be available on the internet.
– anonymous
Aug 11, 2010 at 18:26
• @Chandru1: Both the problem itself and the question of whether or not it has been published somewhere before can be answered. I know the problem itself can be answered because I have seen it published in a text, as noted in my answer. Aug 11, 2010 at 18:30
• The proper term should be (hyper)plane, not boundary. Any surface can be a boundary. Aug 11, 2010 at 18:39

Section 3 of http://www.macalester.edu/~bressoud/pub/Art_of_Counting/Art_of_Counting.pdf discusses the problem for $n=3$ and poses the problem of generalizing to higher dimensions. This article states that the first published solution was by Jakob Steiner in 1826. Other references are cited.

Though not discussed in the full generality you describe, the problem is discussed at length for n = 1, 2, and 3 in Mathematics for High School Teachers: An Advanced Persepective by Usiskin, Peressini, Machisotto, and Stanley (section 5.1.4; © 2003; published by Pearson Education). Specifically, the text uses that problem as an example for discussing how induction can be applied to prove the formulae using the geometry of the problem in the inductive step (when you add the next (n-1)-dimensional boundary object, how many additional regions are created?).

• Thanks, as I don't have the text, are there any references cited? Aug 11, 2010 at 18:30
• @Jamie: The only item in the bibliography for that chapter that looks relevant (if only tangentially so) is "Conway, John, and Richard Guy. The Book of Numbers. New York: Springer-Verlag, 1996, pp. 76–79." with the note "An analysis of the maximum number of regions formed by connecting n points on a circle." Also, mtl.math.uiuc.edu/math-hst is the authors' site for Mathematics for High School Teachers. Aug 11, 2010 at 18:38
• @Jamie: I should add that I had seen versions of this problem before Mathematics for High School Teachers was published, so it is a commonly-used problem. Aug 11, 2010 at 18:39

I presume you are asking for the number of regions into which $n$-space is divided into by $k$ hyperplanes "in general position". See the notes of Richard Stanley on hyperplane arrangements. The answer to your problem is Proposition 2.4, and there are lots more goodies too!

• Interestingly, it's a different Richard Stanley (MIT) than the Richard Stanley who is the 4th author on the book I cited (Berkeley). Aug 11, 2010 at 19:59