Dividing Space
--------------
Call a collection of codimension 1 hyperplanes in R^k independent
if the normals of any j hyperplanes is independent for j <= k.

Call a collection of codimension 1 hyperplanes in R^k porous if no
more than k planes coincide at any point.

Let r(n,k) be the the number of regions into which n independent and
porous hyperplanes divide R^k.  It seems obvious that for n <= k,
r(n,k) = 2^n.

Suppose we know r(n-1,k).  Adding one more hyperplane will add as many
regions as that hyperplane intersects.  That hyperplane intersects as
many regions as the other n-1 hyperplanes divide that hyperplane into.
That is,

    r(n,k) = r(n-1,k) + r(n-1,k-1)                           [1]

Easily, r(0,k) = 1 (no hyperplanes, 1 region).  Also, for n >= 0,
r(n,0) = 1 (there is only 1 region in R^0).  Using [1] to fill in,

    k\n    0    1    2    3    4    5    6    7
    0      1    1    1    1    1    1    1    1
    1      1    2    3    4    5    6    7    8
    2      1    2    4    7   11   16   22   29
    3      1    2    4    8   15   26   42   64              [2]
    4      1    2    4    8   16   31   57   99
    5      1    2    4    8   16   32   63  120
    6      1    2    4    8   16   32   64  127
    7      1    2    4    8   16   32   64  128

It is obvious that each row of table [2] is the difference of the
elements of the next row, and that row 0 is constant.  Thus, row k is
a degree k polynomial of n so that r(n,k) = 2^n for n <= k.  The only
degree k polynomial that satisfies these requirements is

              k
             ---
    r(n,k) = >   C(n,j)                                      [3]
             ---
             j=0

Equation [3] holds for all n,k >= 0 .

Rob Johnson