How many ways can we divide the Space with $N$ lines

combinationscombinatorial-geometrycombinatoricsgeometrysequences-and-series

We know that the maximum number of pieces that can be created with a given number of cuts (lines) $n$, is given by the formula:
$$P_{\max} = \frac{n^2 + n + 2}{2}$$

This is the problem of dividing a pancake or pizza by $n$ cuts, also known as Lazy Caterer's Sequence. A simple proof can be found here in this Wikipedia article: A Pancake Division.

But my question is a little different: How many ways can we divide the space with $n$ lines? So it's not just about getting the most out of formed regions! The figure below shows examples of the problem for better understanding:

enter image description here

Now let $P$ be the number of possible ways, how to determine $P$ as a function of $n$?

Note that it doesn't matter the size or the shape of the regions, but how they are separated in space by the lines.

I think what should be considered is the behavior between the lines, for example, if they are parallel, if they are concurrent, or if they are parallel and concurrent!

The simplest form would be all parallel lines and the most complex form would all be concurrents at different points.

Best Answer

With four lines, there are seven different ways, i.e. numbers of regions into which a bounded space can be divided by four lines. The minimum number of regions is $4+1=5$, produced when no lines intersect within the space.

But every number of regions from $5$ to maximum $11$ is possible. For beginning with $4$ non-intersecting lines within the space, we can add $1, 2, 3$ regions by redrawing one line so as to cut first one, then two, then three other lines, as in the top row of the figure.

Then we add a $4th$ and $5th$ region by redrawing the third line so as to cut one and then both of the first two lines, as in the second row of the figure.

Finally, we get a $6th$ region by making the second line cut the first, as in the third row. How many ways to divide the space Thus to the original five regions we have added$$3+2+1=6$$Generalizing, since the minimum number of regions is $n+1$, and the maximum is$$\frac{n^2+n+2}{2}$$then the number of ways will be$$\frac{n^2+n+2}{2}-n=\frac{n^2-n+2}{2}$$

And since$$\frac{n^2-n+2}{2}=\frac{(n-1)n}{2}+1$$we see that the number of ways $n$ lines can divide the space is equal to the $(n-1)th$ triangle number plus $1$.

Note: This seems to be something more general than a geometric problem. If the space is bounded, no pair of non-intersecting lines need to be parallel. Nor do the line segments need to be straight, provided that no two intersect more than once within the space. And perhaps the only condition on the bounded space is that it be concave from within?

Correction: If the plane is unbounded, and "how many ways" means "how many arrangements," as arrangement is explained in the comments on OEIS A241600 referenced by @Daniel Mathias, then the above is not a suitable answer to the question posted, and there do appear to be nine arrangements of four lines.9 arrangements of four lines The first two rows have parallels, the third does not. There is one 3-line concurrence in the second row, and a 3-line and 4-line concurrence in the third. The number of regions, left to right and top to bottom, is$$5, 8, 9, 9, 10, 10, 8, 10, 11$$Unlike the situation as I first understood it, there are gaps and repetitions in the number of regions produced by the different arrangements. This seems to make the determination of $P$ as a function of $n$ a more difficult task.

Correction continued: $P$ for $n=5$ P for n=5, parallels The figures shows twenty-one arrangements for two or more lines parallel when $n=5$. In each row (except the last, which is actually two rows of two each) four lines keep a given position throughout the row as a fifth line shifts its position through the essentially different arrangements possible. After the first row showing one arrangement each for five and four parallels, the second row has only three parallels, the third has two pairs of two, and the fourth and fifth only two.

Next we can see by a single figure below the arrangements possible when no lines are parallel. Again we suppose the four lines $AB$, $AC$, $FB$, $FD$ given in position. $G$ is any point not collinear with any two of the six intersection points $A$, $B$, $C$, $D$, $E$, $F$. A fifth line through $G$ can pass through and among the six points in $6+7=13$ different ways. 5 lines, 13 ways But if $G$ is collinear with a line $BE$, $DC$, or $AF$, it can be seen even without another figure that the number of possible arrangements will be only $5+6=11$.

And finally, we have one arrangement each for four and five concurrent lines.

Adding them up,$$1+1+5+4+10+13+11+1+1=47$$in agreement with OEIS A241600.