

A000125


Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1,3) + n + 1.
(Formerly M1100 N0419)


77



1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160, 1351, 1562, 1794, 2048, 2325, 2626, 2952, 3304, 3683, 4090, 4526, 4992, 5489, 6018, 6580, 7176, 7807, 8474, 9178, 9920, 10701, 11522, 12384, 13288, 14235, 15226
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Note that a(n) = a(n1) + A000124(n1). This has the following geometrical interpretation: Define a number of planes in space to be in general arrangement when
(1) no two planes are parallel,
(2) there are no two parallel intersection lines,
(3) there is no point common to four or more planes.
Suppose there are already n1 planes in general arrangement, thus defining the maximal number of regions in space obtainable by n1 planes and now one more plane is added in general arrangement. Then it will cut each of the n1 planes and acquire intersection lines which are in general arrangement. (See the comments on A000124 for general arrangement with lines.) These lines on the new plane define the maximal number of regions in 2space definable by n1 straight lines, hence this is A000124(n1). Each of this regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n1) regions already there, hence a(n) = a(n1) + A000124(n1).  Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
More generally, we have: A000027(n) = binomial(n,0) + binomial(n,1) (the natural numbers), A000124(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) (the Lazy Caterer's sequence), a(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3) (Cake Numbers).  Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
If Y is a 2subset of an nset X then, for n>=3, a(n3) is the number of 3subsets of X which do not have exactly one element in common with Y.  Milan Janjic, Dec 28 2007
a(n) is the number of compositions (ordered partitions) of n+1 into four or fewer parts or equivalently the sum of the first four terms in the nth row of Pascal's triangle.  Geoffrey Critzer, Jan 23 2009
a(n) is also the maximum number of different values obtained by summing n consecutive positive integers with all possible 2^n sign combinations. This maximum is first reached when summing the interval [n, 2n1].  Olivier Gérard, Mar 22 2010
a(n) contains only 5 perfect squares > 1: 4, 64, 576, 67600, and 75203584. The incidences of > 0 are given by A047694.  Frank M Jackson, Mar 15 2013
Given n tiles with two values  an A value and a B value  a player may pick either the A value or the B value. The particular tiles are [n, 0], [n1, 1], ..., [2, n2] and [1, n1]. The sequence is the number of different final A:B counts. For example, with n=4, we can have final total [5, 3] = [4, _] + [_, 1] + [_, 2] + [1, _] = [_, 0] + [3, _] + [2, _] + [_, 3], so a(4) = 2^4  1 = 15. The largest and smallest final A+B counts are given by A077043 and A002620 respectively.  Jon Perry, Oct 24 2014
For n>=3, a(n) is also the number of maximal cliques in the (n+1)triangular graph (the 4triangular graph has a(3)=8 maximal cliques).  Andrew Howroyd, Jul 19 2017
a(n) is the number of binary words of length n matching the regular expression 1*0*1*0*. Coincidentally, A000124 counts binary words of the form 0*1*0*. See Alexandersson and Nabawanda for proof.  Per W. Alexandersson, May 15 2021
For n > 0, let the ndimensional cube, {0,1}^n be provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 3. Example: n = 4. Let x = (0,0,0,0) be in {0,1}^4.
d(x,y) = 0: y in {(0,0,0,0)}.
d(x,y) = 1: y in {(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1)}.
d(x,y) = 2: y in {(1,1,0,0), (1,0,1,0), (1,0,0,1), (0,1,1,0), (0,1,0,1), (0,0,1,1)}.
d(x,y) = 3: y in {(1,1,1,0), (1,1,0,1), (1,0,1,1), (0,1,1,1)}.
All these y are at a distance <= 3 from (0,0,0,0), so a(4) = 15. (See Peter C. Heinig's formula).  Yosu Yurramendi, Dec 14 2021
For n >= 2, a(n) is the number of distinct least squares regression lines fitted to n points (j,y_j), 1 <= j <= n, where each y_j is 0 or 1. The number of distinct lines with exactly k 1's among y_1, ..., y_n is A077028(n,k). The number of distinct slopes is A123596(n).  Pontus von Brömssen, Mar 16 2024


REFERENCES

V. I. Arnold (ed.), Arnold's Problems, Springer, 2004, comments on Problem 199011 (p. 75), pp. 503510. Numbers N_3.
R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 27.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
T. H. Stickels, Mindstretching Puzzles. Sterling, NY, 1994 p. 85.
W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #45 (First published: San Francisco: HoldenDay, Inc., 1964)


LINKS

Sebastian Mizera and Sabrina Pasterski, Celestial Geometry, arXiv:2204.02505 [hepth], 2022.


FORMULA

a(n) = (n+1)*(n^2n+6)/6 = (n^3 + 5*n + 6) / 6.
G.f.: (1  2*x + 2x^2)/(1x)^4.  [Simon Plouffe in his 1992 dissertation.]
E.g.f.: (1 + x + x^2/2 + x^3/6)*exp(x).
a(n) = binomial(n,3) + binomial(n,2) + binomial(n,1) + binomial(n,0).  Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Paraphrasing the previous comment: the sequence is the binomial transform of [1,1,1,1,0,0,0,...].  Gary W. Adamson, Oct 23 2007
a(n) = 4*a(n1)  6*a(n2) + 4*a(n3)  a(n4).
Inverse binomial transform of A134396.
Sum_{n>=0} a(n)/n! = 8*exp(1)/3. (End)


EXAMPLE

a(4)=15 because there are 15 compositions of 5 into four or fewer parts. a(6)=42 because the sum of the first four terms in the 6th row of Pascal's triangle is 1+6+15+20=42.  Geoffrey Critzer, Jan 23 2009
For n=5, (1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 35) and their opposite are the 26 different sums obtained by summing 5,6,7,8,9 with any sign combination.  Olivier Gérard, Mar 22 2010
G.f. = 1 + 2*x + 4*x^2 + 8*x^3 + 15*x^4 + 26*x^5 + 42*x^6 + 64*x^7 + ...  Michael Somos, Jul 07 2022


MAPLE



MATHEMATICA

Table[(n^3 + 5 n + 6)/6, {n, 0, 50}] (* Harvey P. Dale, Jan 19 2013 *)
LinearRecurrence[{4, 6, 4, 1}, {1, 2, 4, 8}, 50] (* Harvey P. Dale, Jan 19 2013 *)


PROG

(PARI) Vec((12*x+2*x^2)/((1x)^4) + O(x^100)) \\ Altug Alkan, Oct 16 2015
(Python)
def A000125_gen(): # generator of terms
a, b, c = 1, 1, 1
while True:
yield a
a, b, c = a+b, b+c, c+1


CROSSREFS

Cf. A000124, A003600, A005408, A016813, A086514, A058331, A002522, A161701A161705, A000127, A161706A161708, A080856, A161710A161713, A161715, A006261, A063865, A051601, A077043, A002620, A123596.


KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



