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.

  • 1
    $\begingroup$ 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. $\endgroup$ – joriki Oct 7 '15 at 4:48
  • $\begingroup$ it is the latter. that is would like to see a proof in combinatoric. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ For equality you also need to take care that the ${n \choose 2}$ intersection points are distinct $\endgroup$ – Henry Oct 7 '15 at 9:42
  • $\begingroup$ I have several questions. (1) I thought Euler’s formula is applicable to 3D figures only. How can it be used in this pizza slicing problem? (2) Assuming that (1) can really apply, I am still confused to see what F, V, E’s are. Suppose that we have made 2 cuts to the original pizza. Then, there are 4 pieces => 4 faces? Each piece has 2 edges (excluding the arc –shaped edge) => 8 edges in total? The total number of vertices = 4 (at the rim) + 1 in the interior? (3) If that is true, then for n = 3, (F, V, E) = (7, 6 + 3, 2x6 + 2x3)? $\endgroup$ – Mick Oct 8 '15 at 16:03
  • $\begingroup$ (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. $\endgroup$ – Christian Blatter Oct 8 '15 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.