Lazy caterer's sequence

Last updated
Pancake cut into seven pieces with three straight cuts. PancakeCutThrice.agr.jpg
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 (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; for generalizations to higher dimensions, see arrangement of hyperplanes.

Contents

The analogue of this sequence in three dimensions is the cake numbers.

Formula and sequence

The maximum number of pieces, p obtainable with n straight cuts is the n-th triangular number plus one, forming the lazy caterer's sequence (OEIS A000124) Central polygonal numbers.svg
The maximum number of pieces, p obtainable with n straight cuts is the n-th triangular number plus one, forming the lazy caterer's sequence (OEIS A000124)

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 coefficients, the formula can be expressed as

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

The lazy caterer's sequence (green) and other OEIS sequences in Bernoulli's triangle Bernoulli triangle columns.svg
The lazy caterer's sequence (green) and other OEIS sequences in Bernoulli'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 2.

The sequence can be alternatively derived from the sum of up to the first 3 terms of each row of Pascal's triangle: [1]

k
n
012Sum
01--1
111-2
21214
31337
414611
5151016
6161522
7172129
8182837
9193646

This sequence (sequence A000124 in the OEIS ), starting with n = 0, thus results in

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, ...

Its three-dimensional analogue is known as the cake numbers. The difference between successive cake numbers gives the lazy caterer's sequence. [2]

Proof

The maximum number of pieces from consecutive cuts are the numbers in the Lazy Caterer's Sequence. Lazy Caterer's Sequence (Cuts).gif
The maximum number of pieces from consecutive cuts are the numbers in the Lazy Caterer's Sequence.

When a circle is cut n times to produce the maximum number of pieces, represented as p = f(n), the nth cut must be considered; the number of pieces before the last cut is f(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 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 n cuts is

This recurrence relation can be solved. If f(n 1) is expanded one term, the relation becomes

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

Since f(0) = 1, 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:

See also

Notes

  1. OEIS:  A000124
  2. Yaglom, A. M.; Yaglom, I. M. (1987). Challenging Mathematical Problems with Elementary Solutions. Vol. 1. New York: Dover Publications.

Related Research Articles

<span class="mw-page-title-main">Area</span> Size of a two-dimensional surface

Area is the measure of a region's size on a surface. The area of a plane region or plane area refers to the area of a shape or planar lamina, while surface area refers to the area of an open surface or the boundary of a three-dimensional object. Area can be understood as the amount of material with a given thickness that would be necessary to fashion a model of the shape, or the amount of paint necessary to cover the surface with a single coat. It is the two-dimensional analogue of the length of a curve or the volume of a solid . Two different regions may have the same area ; by synecdoche, "area" sometimes is used to refer to the region, as in a "polygonal area".

<span class="mw-page-title-main">Fibonacci sequence</span> Numbers obtained by adding the two previous ones

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn. The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins

<span class="mw-page-title-main">Golden ratio</span> Number, approximately 1.618

In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if

<span class="mw-page-title-main">Pythagorean triple</span> Integer side lengths of a right triangle

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A triangle whose side lengths are a Pythagorean triple is a right triangle and called a Pythagorean triangle.

<span class="mw-page-title-main">Trigonometric functions</span> Functions of an angle

In mathematics, the trigonometric functions are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all sciences that are related to geometry, such as navigation, solid mechanics, celestial mechanics, geodesy, and many others. They are among the simplest periodic functions, and as such are also widely used for studying periodic phenomena through Fourier analysis.

<span class="mw-page-title-main">Root of unity</span> Number that has an integer power equal to 1

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, and the discrete Fourier transform.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

<span class="mw-page-title-main">Triangular number</span> Figurate 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 nth triangular number is the number of dots in the triangular arrangement with n dots on each side, and is equal to the sum of the n natural numbers from 1 to n. The sequence of triangular numbers, starting with the 0th triangular number, is

In mathematics, a polygonal number is a number that counts dots arranged in the shape of a regular polygon. These are one type of 2-dimensional figurate numbers.

<span class="mw-page-title-main">Centered hexagonal number</span> Number that represents a hexagon with a dot in the center

In mathematics and combinatorics, a centered hexagonal number, or hex number, is a centered figurate number that represents a hexagon with a dot in the center and all other dots surrounding the center dot in a hexagonal lattice. The following figures illustrate this arrangement for the first four centered hexagonal numbers:

The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the OEIS Foundation in 2009. Sloane is the chairman of the OEIS Foundation.

<span class="mw-page-title-main">Centered square number</span> Centered figurate number that gives the number of dots in a square with a dot in the center

In elementary number theory, a centered square number is a centered figurate number that gives the number of dots in a square with a dot in the center and all other dots surrounding the center dot in successive square layers. That is, each centered square number equals the number of dots within a given city block distance of the center dot on a regular square lattice. While centered square numbers, like figurate numbers in general, have few if any direct practical applications, they are sometimes studied in recreational mathematics for their elegant geometric and arithmetic properties.

154 is the natural number following 153 and preceding 155.

<span class="mw-page-title-main">Cake number</span> Concept in combinatorics

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 cube by a plane as a slice made by a knife through a cube-shaped cake. It is the 3D analogue of the lazy caterer's sequence.

277 is the natural number following 276 and preceding 278.

<span class="mw-page-title-main">Square root of 3</span> Unique positive real number which when multiplied by itself gives 3

The square root of 3 is the positive real number that, when multiplied by itself, gives the number 3. It is denoted mathematically as or . It is more precisely called the principal square root of 3 to distinguish it from the negative number with the same property. The square root of 3 is an irrational number. It is also known as Theodorus' constant, after Theodorus of Cyrene, who proved its irrationality.

<span class="mw-page-title-main">Equal incircles theorem</span> On rays from a point to a line, with equal inscribed circles between adjacent rays

In geometry, the equal incircles theorem derives from a Japanese Sangaku, and pertains to the following construction: a series of rays are drawn from a given point to a given line such that the inscribed circles of the triangles formed by adjacent rays and the base line are equal. In the illustration the equal blue circles define the spacing between the rays, as described.

In combinatorial mathematics, the Lobb numberLm,n counts the ways that n + m open parentheses and n − m close parentheses can be arranged to form the start of a valid sequence of balanced parentheses.

<span class="mw-page-title-main">Bernoulli's triangle</span> Array of partial sums of the binomial coefficients

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:

References