# 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 '10 at 18:23
@Chandru1: Why cannot it be answered? – ShreevatsaR Aug 11 '10 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 '10 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. – Isaac Aug 11 '10 at 18:30
The proper term should be (hyper)plane, not boundary. Any surface can be a boundary. – kennytm Aug 11 '10 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? – Jamie Aug 11 '10 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. – Isaac Aug 11 '10 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. – Isaac Aug 11 '10 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). – Isaac Aug 11 '10 at 19:59