Jump to content

Cake number: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
→‎top: Show cake sliced by 3 planes
 
(10 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{short description|Maximum number of regions into which a cube can be partitioned by n cuts}}
{{short description|Concept in combinatorics}}
[[File:cake_number_3.svg|thumb|Three orthogonal planes slice a cake into at most eight (''C''<sub>3</sub>) pieces]]
⚫
[[File:Cake number with 4 cutting planes.gif|thumb|Animation showing the cutting planes required to cut a cake into 15 pieces with 4 slices (representing the 5th cake number). Fourteen of the pieces would have an external surface, with one [[tetrahedron]] cut out of the middle.]]
⚫
In [[mathematics]], the '''cake number''', denoted by ''C<sub>n</sub>'', is the maximum of the number of regions into which a 3-dimensional [[cube]] can be partitioned by exactly ''n'' [[plane (geometry)|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]].


⚫
The values of ''C<sub>n</sub>'' for {{nowrap|1=''n'' = 0, 1, 2, ...}} are given by {{nowrap|1=[[1]], [[2]], [[4]], [[8]], [[15 (number)|15]], 26, 42, 64, 93, 130, 176, 232, ...}} {{OEIS|id=A000125}}.
⚫
[[File:Cake number with 4 cutting planes.gif|thumb|Animation showing the cutting planes required to cut a cake into 15 pieces with 4 slices (representing the 5th cake number). Fourteen of the pieces would have an external surface, with one tetrahedron cut out of the middle.]]
⚫
In [[mathematics]], the '''cake number''', denoted by ''C<sub>n</sub>'', is the maximum number of regions into which a 3-dimensional cube can be partitioned by exactly ''n'' [[plane (geometry)|plane]]s. 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 [[Dividing a circle into areas|circle problem]].

⚫
The values of ''C<sub>n</sub>'' for increasing {{nowrap|1=''n'' ≥ 0}} are given by {{nowrap|1=1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232...}}{{OEIS|id=A000125}}


== General formula ==
== General formula ==


If ''n''! denotes the [[factorial]], and we denote the [[binomial coefficient]]s by
If ''n''! denotes the [[factorial]], and we denote the [[binomial coefficient]]s by
:<math> {n \choose k} = \frac{n!}{k! \, (n-k)!} , </math>
:<math>{n \choose k} = \frac{n!}{k!(n-k)!},</math>
and we assume that ''n'' planes are available to partition the cube, then the ''n''-th cake number is:<ref name="Yaglom-Yaglom">{{cite book|last1=Yaglom |first1=A. M. |authorlink1=Akiva Yaglom |last2=Yaglom |first2=I. M. |authorlink2=Isaak Yaglom |title=Challenging Mathematical Problems with Elementary Solutions |volume=1 |location=New York |publisher=[[Dover Publications]] |year=1987}}</ref>
and we assume that ''n'' planes are available to partition the cube, then the ''n''-th cake number is:<ref name="Yaglom-Yaglom">{{cite book|last1=Yaglom |first1=A. M. |authorlink1=Akiva Yaglom |last2=Yaglom |first2=I. M. |authorlink2=Isaak Yaglom |title=Challenging Mathematical Problems with Elementary Solutions |volume=1 |location=New York |publisher=[[Dover Publications]] |year=1987}}</ref>
:<math>
:<math>
C_n = {n \choose 3} + {n \choose 2} + {n \choose 1} + {n \choose 0} = \tfrac{1}{6}\left(n^3 + 5n + 6\right) = \tfrac{1}{6}\left(n+1) (n (n-1) + 6\right). </math>
C_n = {n \choose 3} + {n \choose 2} + {n \choose 1} + {n \choose 0} = \tfrac{1}{6}\!\left(n^3 + 5n + 6\right) = \tfrac{1}{6}(n+1)\left(n(n-1) + 6\right).</math>


==Properties==
==Properties==
The only cake number which is [[prime number|prime]] is [[2 (number)|2]], since it requires <math>\left(n+1) (n (n-1) + 6\right)</math> to have prime factorisation <math>2 \cdot 3 \cdot p</math> where <math>p</math> is some prime. This is impossible for <math>n > 2</math> as we know <math>\left(n (n-1) + 6\right)</math> must be even, so it must be equal to <math>2</math>, <math>2 \cdot 3</math>, <math>2 \cdot p</math>, or <math>2 \cdot 3 \cdot p</math>, which correspond to the cases: <math>\left(n (n-1) + 6\right) = 2</math> (which has only complex roots), <math>\left(n (n-1) + 6\right) = 6</math> (i.e. <math>n \in \{0,1\}</math>), <math>(n+1) = 3</math>, and <math>(n+1) = 1</math>.{{citation needed|reason=This is a valid proof, but it needs a published reference nonetheless.|date=August 2021}}

The cake numbers are the 3-dimensional analogue of the 2-dimensional [[lazy caterer's sequence]]. The difference between successive cake numbers also gives the lazy caterer's sequence.<ref name="Yaglom-Yaglom"/>
The cake numbers are the 3-dimensional analogue of the 2-dimensional [[lazy caterer's sequence]]. The difference between successive cake numbers also gives the lazy caterer's sequence.<ref name="Yaglom-Yaglom"/>


Line 22: Line 20:
The fourth column of [[Bernoulli's triangle]] (''k'' = 3) gives the cake numbers for ''n'' cuts, where ''n'' &ge; 3.
The fourth column of [[Bernoulli's triangle]] (''k'' = 3) gives the cake numbers for ''n'' cuts, where ''n'' &ge; 3.


The sequence can be alternatively derived from the sum of up to the first 4 terms of each row of [[Pascal's triangle]]<ref>{{oeis|A000125}}</ref>
The sequence can be alternatively derived from the sum of up to the first 4 terms of each row of [[Pascal's triangle]]:<ref>{{oeis|A000125}}</ref>
{{table alignment}}
:{| class="wikitable" style="text-align:right;"
:{| class="wikitable defaultright col1center"
! {{diagonal split header|''n''|''k''}} !! 0 !! 1 !! 2 !! 3
! {{diagonal split header|''n''|''k''}} !! 0 !! 1 !! 2 !! 3
! rowspan="11" style="padding:0;"| !! Sum
! rowspan="11" style="padding:0;"| !! Sum
|-
|-
! 0
! style="text-align:left;"|{{figure space}}1
| 1 || - || - || - || 1
| 1 || — || — || — || 1
|-
|-
! 1
! style="text-align:left;"|{{figure space}}2
| 1 || 1 || - || - || 2
| 1 || 1 || — || — || 2
|-
|-
! 2
! style="text-align:left;"|{{figure space}}3
| 1 || 2 || 1 || - || 4
| 1 || 2 || 1 || — || 4
|-
|-
! 3
! style="text-align:left;"|{{figure space}}4
| 1 || 3 || 3 || 1 || 8
| 1 || 3 || 3 || 1 || 8
|-
|-
! 4
! style="text-align:left;"|{{figure space}}5
| 1 || 4 || 6 || 4 || 15
| 1 || 4 || 6 || 4 || 15
|-
|-
! 5
! style="text-align:left;"|{{figure space}}6
| 1 || 5 || 10 || 10 || 26
| 1 || 5 || 10 || 10 || 26
|-
|-
! 6
! style="text-align:left;"|{{figure space}}7
| 1 || 6 || 15 || 20 || 42
| 1 || 6 || 15 || 20 || 42
|-
|-
! 7
! style="text-align:left;"|{{figure space}}8
| 1 || 7 || 21 || 35 || 64
| 1 || 7 || 21 || 35 || 64
|-
|-
! 8
! style="text-align:left;"|{{figure space}}9
| 1 || 8 || 28 || 56 || 93
| 1 || 8 || 28 || 56 || 93
|-
|-
! 9
! style="text-align:left;"|10
| 1 || 9 || 36 || 84 || 130
| 1 || 9 || 36 || 84 || 130
|}
|}

== Other applications ==

In ''n'' spatial (not spacetime) dimensions, [[Maxwell's equations]] represent <math>C_n</math> different independent real-valued equations.


== References ==
== References ==
Line 68: Line 71:


[[Category:Mathematical optimization]]
[[Category:Mathematical optimization]]
[[Category:Integer sequences]]




Latest revision as of 00:36, 6 July 2024

Three orthogonal planes slice a cake into at most eight (C3) pieces
Animation showing the cutting planes required to cut a cake into 15 pieces with 4 slices (representing the 5th cake number). Fourteen of the pieces would have an external surface, with one tetrahedron cut out of the middle.

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.

The values of Cn for n = 0, 1, 2, ... are given by 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, ... (sequence A000125 in the OEIS).

General formula

[edit]

If n! denotes the factorial, and we denote the binomial coefficients by

and we assume that n planes are available to partition the cube, then the n-th cake number is:[1]

Properties

[edit]

The cake numbers are the 3-dimensional analogue of the 2-dimensional lazy caterer's sequence. The difference between successive cake numbers also gives the lazy caterer's sequence.[1]

Cake numbers (blue) and other OEIS sequences in Bernoulli's triangle

The fourth column of Bernoulli's triangle (k = 3) gives the cake numbers for n cuts, where n ≥ 3.

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

k
n
 0 1 2 3 Sum
0 1 — — — 1
1 1 1 — — 2
2 1 2 1 — 4
3 1 3 3 1 8
4 1 4 6 4 15
5 1 5 10 10 26
6 1 6 15 20 42
7 1 7 21 35 64
8 1 8 28 56 93
9 1 9 36 84 130

Other applications

[edit]

In n spatial (not spacetime) dimensions, Maxwell's equations represent different independent real-valued equations.

References

[edit]
  1. ^ a b Yaglom, A. M.; Yaglom, I. M. (1987). Challenging Mathematical Problems with Elementary Solutions. Vol. 1. New York: Dover Publications.
  2. ^ OEIS: A000125
[edit]


Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cake_number&oldid=1232861317"