# A question about the proof of the “Lazy caterer's sequence”

A question about the proof of the “Lazy caterer's sequence”

In https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence , Wiki provides formulas:-

The maximum number p of pieces that can be created with a given number of cuts n, where n ≥ 0, is given by the formula

$$p = \dfrac {n^2 + n + 2}{2}$$

Using binomial coefficients, the formula can be expressed as

$$p = {n+1 \choose 2} + 1 = {n \choose 2} + {n \choose 1} +{n \choose 0}$$

It proves the first in great details but says very little about the second and the third. I would like to know the missing details.

• It's not entirely clear to me whether you want the arithmetic details of why these three forms are equivalent, or whether you're interested in combinatoric interpretations of the fact that the result can be expressed in this way using binomial coefficients. – joriki Oct 7 '15 at 4:48
• it is the latter. that is would like to see a proof in combinatoric. – Mick Oct 7 '15 at 8:07

Let the lines end at the rim of the pizza. Not counting the exterior of the pizza we have, according to Euler's formula, $$f-e+v=1\ ,$$ where $f$ is the number of faces, $e$ the number of edges, and $v=v_3+v_4$ the number of vertices in the resulting configuration. If no three cuts go through the same point there are $v_3=2n$ vertices of degree $3$ along the rim of the pizza and $v_4$ vertices of degree $4$ in its interior. From $2e=3v_3+4v_4$ it follows that $e=3n+2v_4$. Inserting this into $(1)$ we therefore obtain $$f=3n+2v_4-(2n+v_4)+1=v_4+n+1\leq{n\choose 2}+{n\choose 1}+{n\choose0}\ ,$$ with equality iff we take care that all ${n\choose2}$ intersection points of the cuts are within the pizza.
• For equality you also need to take care that the ${n \choose 2}$ intersection points are distinct – Henry Oct 7 '15 at 9:42
• (1) Euler's formula can be applied to a "map" in the plane, whereby the "exterior" counts as a face. (2) $f$ denotes the number of pieces, $v$ the number of points where two cuts meet or a cut meets the rim of the pizza, and $e$ is the number of segments and arcs on the rim between two vertices. (3) Two cuts generate four pieces, four vertices on the rim and one vertex in the interior. Four edges are on the rim and four edges connect the vertex in the interior with a vertex on the rim. – I had assumed tat you were familiar with such ideas. – Christian Blatter Oct 8 '15 at 18:08