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

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: 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.

• OEIS: A241600 – Daniel Mathias Mar 12 '20 at 3:18
• I think the number of regions can be cut out is no less than $2n$, with n is the number of lines used. The number of regions varies from $2n$ to $\frac{n^2+n+1}{2}$. We just need an induction method to show how it's done – Nikola Tolzsek Mar 14 '20 at 11:22
• I have added to my corrected answer, working out $P$ for $n=5$. Still no general rule, but perhaps some progress. Hard to see how to verify $791$ for $P=6$ (never mind $37830$ for $n=7$), which might give added insight into a possible general expression for $P$ as a function of $N$. – Edward Porcella Mar 24 '20 at 20:33

## 1 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. 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. 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$$ 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. 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.

• There are nine ways with four lines. See link in my comment above. – Daniel Mathias Mar 19 '20 at 19:08
• Thanks Edward! You did an analysis limiting the space by a circle, generating a solution to another problem. Distinct regions are generated when we limit the space where the intersections of the lines occur. Notice in the first row figures where 1 line is not parallel to the others, it will cut all the others in the open space, so all these figures, in reality, represent the same way, and must count only one mode. – Fractall Mar 20 '20 at 14:37
• Right, I'm afraid I misrepresented your question. Removing the boundary, and understanding "ways" as "arrangements", as explained in the comment section of OEIS: A241600, which @Daniel Mathias refers us to, I believe I do find 9 different arrangements for $n=4$. I'll submit them in an addendum (comment welcome), but that may be the best I can do. Determining $P$ as a function of $n$ looks like a daunting task. – Edward Porcella Mar 20 '20 at 15:40
• Thank you Edward! Your illustrations and analysis help you to better understand the problem. His idea seems to be very promising when he separates the figures according to the behavior of the lines (parallel, concurrence, etc.). We could think of something like this: fixing a situation (3 concurrences, for example) and leaving the 4th line free, how many ways could this free line match the fixed situation? The idea would be to study cases of parallelisms and concurrences. – Fractall Mar 22 '20 at 15:34