View source for Lazy caterer's sequence

{{Short description|Counts pieces of a disk cut by lines}}
[[Image:PancakeCutThrice.agr.jpg|thumb|Pancake cut into seven pieces with three straight cuts.]]
The '''lazy caterer's sequence,''' more formally known as the '''central polygonal numbers''', describes the maximum number of pieces of a [[Disk (mathematics)|disk]] (a pancake or pizza is usually used to describe the situation) that can be made with a given number of straight cuts. For example, three cuts across a pancake will produce six pieces if the cuts all meet at a common point inside the circle, but up to seven if they do not. This problem can be formalized mathematically as one of counting the cells in an [[Arrangement of lines|arrangement of lines]]; for generalizations to higher dimensions, ''see'' [[Arrangement of hyperplanes|arrangement of hyperplanes]].

The analogue of this [[Integer sequence|sequence]] in three dimensions is the [[Cake number|cake number]]s.

==Formula and sequence==
The maximum number ''p'' of pieces that can be created with a given number of cuts {{math|''n''}} (where {{math|''n'' ≥ 0}}) is given by the formula

:<math>p = \frac{n^2+n+2}{2}.</math>

Using [[Binomial coefficient|binomial coefficient]]s, the formula can be expressed as

:<math>p = 1 + \dbinom{n + 1}{2} = \dbinom{n}{0}+\dbinom{n}{1}+\dbinom{n}{2}. </math>

Simply put, each number equals a [[Triangular number|triangular number]] plus 1. These are the first number on each row of [[Floyd's triangle]].

As the third column of [[Bernoulli's triangle]] (''k'' = 2) is a triangular number plus one, it forms the lazy caterer's sequence for ''n'' cuts, where ''n'' &ge; 2.

The sequence can be alternatively derived from the sum of up to the first 3 terms of each row of [[Pascal's triangle]]:<ref>{{oeis|A000124}}</ref>
:{| class="wikitable" style="text-align:right;"
! {{diagonal split header|''n''|''k''}} !! 0 !! 1 !! 2
! rowspan="11" style="padding:0;"| !! Sum
|-
! style="text-align:left;"|{{figure space}}0
| 1 || - ||  - ||  1
|-
! style="text-align:left;"|{{figure space}}1
| 1 || 1 ||  - ||  2
|-
! style="text-align:left;"|{{figure space}}2
| 1 || 2 ||  1 ||  4
|-
! style="text-align:left;"|{{figure space}}3
| 1 || 3 ||  3 ||  7
|-
! style="text-align:left;"|{{figure space}}4
| 1 || 4 ||  6 || 11
|-
! style="text-align:left;"|{{figure space}}5
| 1 || 5 || 10 || 16
|-
! style="text-align:left;"|{{figure space}}6
| 1 || 6 || 15 || 22
|-
! style="text-align:left;"|{{figure space}}7
| 1 || 7 || 21 || 29
|-
! style="text-align:left;"|{{figure space}}8
| 1 || 8 || 28 || 37
|-
! style="text-align:left;"|{{figure space}}9
| 1 || 9 || 36 || 46
|}

This sequence {{OEIS|id=A000124}}, starting with {{math|''n'' {{=}} 0}}, thus results in

:[[1|1]], [[2|2]], [[4|4]], [[7|7]], [[11 (number)|11]], [[16 (number)|16]], [[22 (number)|22]], [[29 (number)|29]], [[37 (number)|37]], [[46 (number)|46]], [[56 (number)|56]], [[67 (number)|67]], [[79 (number)|79]], [[92 (number)|92]], [[106 (number)|106]], [[121 (number)|121]], [[137 (number)|137]], [[154 (number)|154]], [[172 (number)|172]], [[191 (number)|191]], [[211 (number)|211]], ...

Its three-dimensional analogue is known as the [[Cake number|cake number]]s. The difference between successive cake numbers gives the lazy caterer's sequence.<ref>{{cite book|last1=Yaglom |first1=A. M. |last2=Yaglom |first2=I. M. |title=Challenging Mathematical Problems with Elementary Solutions |volume=1 |location=New York |publisher=[[Social:Dover Publications|Dover Publications]] |year=1987}}</ref>

==Proof==
[[File:Lazy Caterer's Sequence (Cuts).gif|thumb|The maximum number of pieces from consecutive cuts are the numbers in the Lazy Caterer's Sequence.]]
When a circle is cut {{math|''n''}} times to produce the maximum number of pieces, represented as {{math|''p'' {{=}} ''f''&thinsp;(''n'')}}, the {{math|''n''}}th cut must be considered; the number of pieces before the last cut is {{math|''f''&thinsp;(''n''&nbsp;−&thinsp;1)}}, while the number of pieces added by the last cut is {{math|''n''}}.

To obtain the maximum number of pieces, the {{math|''n''}}th cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the {{math|''n''}}th line itself is cut in {{math|''n''&nbsp;−&thinsp;1}} places, and into {{math|''n''}} line segments.  Each segment divides one piece of the {{math|(''n''&nbsp;−&thinsp;1)}}-cut pancake into 2 parts, adding exactly {{math|''n''}} to the number of pieces. The new line cannot have any more segments since it can only cross each previous line once.  A cut line can always cross over all previous cut lines, as rotating the knife at a small [[Angle|angle]] around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.

Thus, the total number of pieces after {{math|''n''}} cuts is

:<math>f(n) = n+f(n-1).</math>

This [[Recurrence relation|recurrence relation]] can be solved.  If {{math|''f''&thinsp;(''n''&nbsp;−&thinsp;1)}} is expanded one term, the relation becomes

:<math>f(n) = n+(n-1)+f(n-2).</math>

Expansion of the term {{math|''f''&thinsp;(''n'' − 2)}} can continue until the last term is reduced to {{math|''f''&thinsp;(0)}}, thus,

:<math>f(n) = n+(n-1)+(n-2)+\cdots+1+f(0).</math>

Since {{math|''f''&thinsp;(0) {{=}} 1}}, because there is one piece before any cuts are made, this can be rewritten as

:<math>f(n) = 1+(1+2+3+\cdots + n).</math>

This can be simplified, using the formula for the sum of an [[Arithmetic progression|arithmetic progression]]:

:<math>f(n)=1+\frac{n(n+1)}{2}=\frac{n^2+n+2}{2}.</math>

==See also==
*[[Cake number]]
*[[Floyd's triangle]]
*[[Dividing a circle into areas]] &ndash; where ''n'' is the number of sides of an inscribed polygon

==Notes==
{{reflist}}

==References==
*{{citation
 | last = Moore | first = T. L.
 | issue = 2
 | journal = The College Mathematics Journal
 | pages = 125–130
 | title = Using Euler's formula to solve plane separation problems
 | jstor = 2686448
 | volume = 22
 | year = 1991
 | doi = 10.2307/2686448
 | publisher = Mathematical Association of America}}.

*{{citation
 | journal = [[Crelle's Journal|J. Reine Angew. Math.]]
 | pages = 349–364
 | title = Einige Gesetze über die Theilung der Ebene und des Raumes ("A Few Statements about the Division of the Plane and of Space")
 | volume = 1
 | year = 1826}}.

*{{citation
 | last = Wetzel
 | first = J. E.
 | issue = 8
 | journal = American Mathematical Monthly
 | pages = 647–656
 | title = On the division of the plane by lines
 | url = http://webcourse.cs.technion.ac.il/236603/Spring2008/ho/WCFiles/Wetzel.pdf
 | volume = 85
 | year = 1978
 | doi = 10.2307/2320333
 | publisher = Mathematical Association of America
 | jstor = 2320333
 | access-date = 2008-12-15
 | archive-url = https://web.archive.org/web/20110721134954/http://webcourse.cs.technion.ac.il/236603/Spring2008/ho/WCFiles/Wetzel.pdf
 | archive-date = 2011-07-21
 | url-status = dead
 }}.

==External links==
*{{mathworld|title=Circle Division by Lines|urlname=CircleDivisionbyLines}}

[[Category:Mathematical optimization]]
[[Category:Integer sequences]]
[[Category:Articles containing proofs]]

{{Sourceattribution|Lazy caterer's sequence}}