Lazy caterer's sequence
Encyclopedia
The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a circle
Circle
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....

 (a pancake
Pancake
A pancake is a thin, flat, round cake prepared from a batter, and cooked on a hot griddle or frying pan. Most pancakes are quick breads; some use a yeast-raised or fermented batter. Most pancakes are cooked one side on a griddle and flipped partway through to cook the other side...

 or pizza
Pizza
Pizza is an oven-baked, flat, disc-shaped bread typically topped with a tomato sauce, cheese and various toppings.Originating in Italy, from the Neapolitan cuisine, the dish has become popular in many parts of the world. An establishment that makes and sells pizzas is called a "pizzeria"...

 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, but 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
In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.-Definition:For any...

; for generalizations to higher dimensions, see arrangement of hyperplanes
Arrangement of hyperplanes
In geometry and combinatorics, an arrangement of hyperplanes is a finite set A of hyperplanes in a linear, affine, or projective space S....

.

The analogue of this sequence in 3 dimensions is the cake number
Cake number
In mathematics, the cake number, denoted by Cn, is the maximum number of regions into which a 3-dimensional cube can be partitioned by exactly n planes...

.

Formula and sequence

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


Using binomial coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...

s, the formula can be expressed as


This sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...

 , starting with , results in
1, 2, 4, 7, 11
11 (number)
11 is the natural number following 10 and preceding 12.Eleven is the first number which cannot be counted with a human's eight fingers and two thumbs additively. In English, it is the smallest positive integer requiring three syllables and the largest prime number with a single-morpheme name...

, 16
16 (number)
16 is the natural number following 15 and preceding 17. 16 is a composite number, and a square number, being 42 = 4 × 4. It is the smallest number with exactly five divisors, its proper divisors being , , and ....

, 22
22 (number)
22 is the natural number following 21 and preceding 23.- In mathematics :Twenty-two is an even composite number, its proper divisors being 1, 2 and 11....

, 29
29 (number)
29 is the natural number following 28 and preceding 30.-In mathematics:It is the tenth prime number, and also the fourth primorial prime. It forms a twin prime pair with thirty-one, which is also a primorial prime. Twenty-nine is also the sixth Sophie Germain prime. It is also the sum of three...

, 37
37 (number)
37 is the natural number following 36 and preceding 38.-In mathematics:It is a prime number, the fifth lucky prime, the first irregular prime, the third unique prime and the third cuban prime of the form...

, 46
46 (number)
46 is the natural number following 45 and preceding 47.- In mathematics :Forty-six is a Wedderburn-Etherington number, an enneagonal number and a centered triangular number. It is the sum of the totient function for the first twelve integers. 46 is the largest even integer that can't be expressed...

, 56
56 (number)
56 is the natural number following 55 and preceding 57.- Mathematics :56 is the sum of the first six triangular numbers , as well as the sum of six consecutive primes . It is also a tetranacci number and a pronic number. Adding up the divisors of 1 through 8 gives 56...

, 67
67 (number)
67 is the natural number following 66 and preceding 68. It is an odd number.-In mathematics:Sixty-seven is the 19th prime number , an irregular prime, a lucky prime, the sum of five consecutive primes , and a Heegner number.Since 18! + 1 is divisible by 67 but 67 is not one more than a multiple of...

, 79
79 (number)
Seventy-nine is the natural number following 78 and preceding 80.79 may represent:-In mathematics:*An odd number*The smallest number that can't be represented as a sum of fewer than 19 fourth powers*A strictly non-palindromic number...

, 92
92 (number)
92 is the natural number following 91 and preceding 93.- In mathematics:Ninety-two is a pentagonal number.There are 92 Johnson solids...

, 106
106 (number)
106 is the natural number following 105 and preceding 107.-In mathematics:106 is the thirty-first distinct biprime and the fifteenth of the form...

, 121
121 (number)
121 is the natural number following 120 and preceding 122.-In mathematics:One hundred [and] twenty-one is a square and is the sum of three consecutive primes . There are no squares besides 121 known to be of the form 1 + p + p^2 + p^3 + p^4, where p is prime...

, 137
137 (number)
137 is the natural number following 136 and preceding 138.-In mathematics :One hundred [and] thirty-seven is the 33rd prime number; the next is 139, with which it comprises a twin prime, and thus 137 is a Chen prime. 137 is an Eisenstein prime with no imaginary part and a real part of the form 3n -...

, 154
154 (number)
One hundred and fifty-four is the natural number following one hundred and fifty-three and preceding one hundred and fifty-five.-In mathematics:* 154 is a nonagonal number...

, 172
172 (number)
172 is the natural number following 171 and preceding 173.-In mathematics:* 172 is an even number* 172 is a composite number* 172 is a deficient number* 172 is a noncototient integer...

, 191
191 (number)
191 is the natural number following 190 and preceding 192.-In mathematics:* 191 is an odd number* 191 is a centered 19-gonal number* 191 is a deficient number, as 1 is less than 191...

, 211
211 (number)
211 is the natural number between 210 and 212. It is also a prime number.-In mathematics:211 is an odd number.211 is a primorial prime, sum of three consecutive primes , Chen prime, centered decagonal prime, and self prime....

, ...


Each number equals 1 plus a triangular number
Triangular number
A triangular number or triangle number numbers the objects that can form an equilateral triangle, as in the diagram on the right. The nth triangle number is the number of dots in a triangle with n dots on a side; it is the sum of the n natural numbers from 1 to n...

.

Proof

When a circle is cut n times to produce the maximum number of pieces, represented as p = ƒ(n), the nth cut must be considered; the number of pieces before the last cut is ƒ(n − 1), while the number of pieces added by the last cut is n.

To obtain the maximum number of pieces, the nth cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the nth line itself is cut in n − 1 places, and into n line segments. Each segment divides one piece of the (n − 1)-cut pancake into 2 parts, adding exactly n to the number of pieces. The new line can't 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 n cuts is


This recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

 can be solved. If ƒ(n − 1) is expanded one term the relation becomes


Expansion of the term ƒ(n − 2) can continue until the last term is reduced to ƒ(0), thus,


Since , because there is one piece before any cuts are made, this can be rewritten as


This can be simplified, using the formula for the sum of an arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...

:
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK