Lazy caterer's sequence
   HOME

TheInfoList



OR:

The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a
disk Disk or disc may refer to: * Disk (mathematics), a geometric shape * Disk storage Music * Disc (band), an American experimental music band * ''Disk'' (album), a 1995 EP by Moby Other uses * Disk (functional analysis), a subset of a vector sp ...
(a
pancake A pancake (or hotcake, griddlecake, or flapjack) is a flat cake, often thin and round, prepared from a Starch, starch-based batter (cooking), batter that may contain eggs, milk and butter and cooked on a hot surface such as a griddle or fryi ...
or
pizza Pizza (, ) is a dish of Italian origin consisting of a usually round, flat base of leavened wheat-based dough topped with tomatoes, cheese, and often various other ingredients (such as various types of sausage, anchovies, mushrooms, onions ...
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 In music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orchestr ...
; for generalizations to higher dimensions, ''see''
arrangement of hyperplanes In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''. Questions about a hyperplane arrangement ''A'' generally concern geometrical, ...
. The analogue of this sequence in three dimensions is the
cake number In mathematics, the cake number, denoted by ''Cn'', is the maximum of the number of regions into which a 3-dimensional cube can be partitioned by exactly ''n'' planes. The cake number is so-called because one may imagine each partition of the cu ...
.


Formula and sequence

The maximum number ''p'' of pieces that can be created with a given number of cuts , where , is given by the formula : p = \frac. Using
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s, the formula can be expressed as :p = 1 + \dbinom = \dbinom+\dbinom+\dbinom. Simply put, each number equals a
triangular number A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...
plus 1. As the third column of
Bernoulli's triangle Bernoulli's triangle is an array of partial sums of the binomial coefficients. For any non-negative integer ''n'' and for any integer ''k'' included between 0 and ''n'', the component in row ''n'' and column ''k'' is given by: : \sum_^k , i ...
(''k'' = 2) is a triangular number plus one, it forms the lazy caterer's sequence for ''n'' cuts, where ''n'' ≥ 2. The sequence can be alternatively derived from the sum of up to the first 3 terms of each row of
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
: : This
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
, starting with , thus results in : 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121,
137 137 may refer to: *137 (number) *137 BC *AD 137 *137 (album), an album by The Pineapple Thief *137 (MBTA bus) The Massachusetts Bay Transportation Authority bus division operates bus routes in the Boston, Massachusetts metropolitan area. All ro ...
, 154,
172 Year 172 ( CLXXII) was a leap year starting on Tuesday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Scipio and Maximus (or, less frequently, year 925 '' Ab urbe condita ...
, 191, 211, ... Its three-dimensional analogue is known as the
cake number In mathematics, the cake number, denoted by ''Cn'', is the maximum of the number of regions into which a 3-dimensional cube can be partitioned by exactly ''n'' planes. The cake number is so-called because one may imagine each partition of the cu ...
s. The difference between successive cake numbers gives the lazy caterer's sequence.


Proof

When a circle is cut times to produce the maximum number of pieces, represented as , the th cut must be considered; the number of pieces before the last cut is , while the number of pieces added by the last cut is . To obtain the maximum number of pieces, the 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 th line itself is cut in places, and into line segments. Each segment divides one piece of the -cut pancake into 2 parts, adding exactly 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 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 cuts is :f(n)=n+f(n-1). This
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
can be solved. If is expanded one term the relation becomes :f(n)=n+(n-1)+f(n-2). Expansion of the term can continue until the last term is reduced to , thus, :f(n)=n+(n-1)+(n-2)+\cdots+1+f(0). Since , because there is one piece before any cuts are made, this can be rewritten as :f(n)=1+(1+2+3+\cdots + n). This can be simplified, using the formula for the sum of an
arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
: :f(n)=1+\frac=\frac.


See also

*
Cake number In mathematics, the cake number, denoted by ''Cn'', is the maximum of the number of regions into which a 3-dimensional cube can be partitioned by exactly ''n'' planes. The cake number is so-called because one may imagine each partition of the cu ...
* Floyd's triangle *
Dividing a circle into areas The number of and for first 6 terms of Moser's circle problem In geometry, the problem of dividing a circle into areas by means of an inscribed polygon with ''n'' sides in such a way as to ''maximise'' the number of areas created by the edges an ...
– where ''n'' is the number of sides of an inscribed polygon


Notes


References

*. *. *.


External links

*{{mathworld, title=Circle Division by Lines, urlname=CircleDivisionbyLines Mathematical optimization Integer sequences Articles containing proofs