

A000124


Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts.
(Formerly M1041 N0391)


278



1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

These are Hogben's central polygonal numbers with the (twodimensional) symbol
2
.P
1 n
The first line cuts the pancake into 2 pieces. For n > 1, the nth line crosses every earlier line (avoids parallelism) and also avoids every previous line intersection, thus increasing the number of pieces by n. For 16 lines, for example, the number of pieces is 2 + 2 + 3 + 4 + 5 + ... + 16 = 137. These are the triangular numbers plus 1 (cf. A000217).
m = (n1)(n2)/2 + 1 is also the smallest number of edges such that all graphs with n nodes and m edges are connected.  Keith M. Briggs, May 14 2004
Also maximal number of grandchildren of a binary vector of length n+2. E.g., a binary vector of length 6 can produce at most 11 different vectors when 2 bits are deleted.
This is also the order dimension of the (strong) Bruhat order on the finite Coxeter group B_{n+1}.  Nathan Reading (reading(AT)math.umn.edu), Mar 07 2002
Number of 132 and 321avoiding permutations of {1,2,...,n+1}.  Emeric Deutsch, Mar 14 2002
For n >= 1 a(n) is the number of terms in the expansion of (x+y)*(x^2+y^2)*(x^3+y^3)*...*(x^n+y^n).  Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
Also the number of terms in (1)(x+1)(x^2+x+1)...(x^n+...+x+1); see A000140.
Narayana transform (analog of the binomial transform) of vector [1, 1, 0, 0, 0, ...] = A000124; using the infinite lower Narayana triangle of A001263 (as a matrix), N; then N * [1, 1, 0, 0, 0, ...] = A000124.  Gary W. Adamson, Apr 28 2005
a(n) = A108561(n+3,2).  Reinhard Zumkeller, Jun 10 2005
Number of interval subsets of {1,2,3,...,n} (cf. A002662).  Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
Define a number of straight lines in the plane to be in general arrangement when (1) no two lines are parallel, (2) there is no point common to three lines. Then these are the maximal numbers of regions defined by n straight lines in general arrangement in the plane.  Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Note that a(n) = a(n1) + A000027(n1). This has the following geometrical interpretation: Suppose there are already n1 lines in general arrangement, thus defining the maximal number of regions in the plane obtainable by n1 lines and now one more line is added in general arrangement. Then it will cut each of the n1 lines and acquire intersection points which are in general arrangement. (See the comments on A000027 for general arrangement with points.) These points on the new line define the maximal number of regions in 1space definable by n1 points, hence this is A000027(n1), where for A000027 an offset of 0 is assumed, that is, A000027(n1) = (n+1)1 = n. Each of these 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) + A000027(n1). Cf. the comments on A000125 for an analogous interpretation.  Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
When constructing a zonohedron, one zone at a time, out of (up to) 3d nonintersecting parallelepipeds, the nth element of this sequence is the number of edges in the nth zone added with the nth "layer" of parallelepipeds. (Verified up to 10zone zonohedron, the enneacontahedron.) E.g., adding the 10th zone to the enneacontahedron requires 46 parallel edges (edges in the 10th zone) by looking directly at a 5valence vertex and counting visible vertices.  Shel Kaphan, Feb 16 2006
Binomial transform of (1, 1, 1, 0, 0, 0, ...) and inverse binomial transform of A072863: (1, 3, 9, 26, 72, 192, ...).  Gary W. Adamson, Oct 15 2007
If Y is a 2subset of an nset X then, for n >= 3, a(n3) is the number of (n2)subsets of X which have no exactly one element in common with Y.  Milan Janjic, Dec 28 2007
Equals row sums of triangle A144328.  Gary W. Adamson, Sep 18 2008
It appears that a(n) is the number of distinct values among the fractions F(i+1)/F(j+1) as j ranges from 1 to n and, for each fixed j, i ranges from 1 to j, where F(i) denotes the ith Fibonacci number.  John W. Layman, Dec 02 2008
a(n) is the number of subsets of {1,2,...,n} that contain at most two elements.  Geoffrey Critzer, Mar 10 2009
For n >= 2, a(n) gives the number of sets of subsets A_1, A_2, ..., A_n of n={1,2,...,n} so that $\cap_{i=1}^{n} A_i=\emptyset$ and the sum $\sum_{\forall j\in [n]}\left (\cap_{i=1,i\ne j}^{n} A_i\right )$ is maximum.  Srikanth K S, Oct 22 2009
The numbers along the left edge of Floyd's triangle.  Paul Muljadi, Jan 25 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = A[i,i]:=1, A[i,i1] = 1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n1) = (1)^(n1)*coeff(charpoly(A,x),x).  Milan Janjic, Jan 24 2010
Also the number of deck entries of Euler's ship. See the MeijerNepveu link.  Johannes W. Meijer, Jun 21 2010
(1 + x^2 + x^3 + x^4 + x^5 + ...)*(1 + 2x + 3x^2 + 4x^3 + 5x^4 + ...) = (1 + 2x + 4x^2 + 7x^3 + 11x^4 + ...).  Gary W. Adamson, Jul 27 2010
The number of length n binary words that have no 0digits between any pair of consecutive 1digits.  Jeffrey Liese, Dec 23 2010
Let b(0) = b(1) = 1; b(n) = max(b(n1)+n1, b(n2)+n2) then a(n) = b(n+1).  Yalcin Aktar, Jul 28 2011
Also number of triangular numbers so far, for n > 0: a(n) = a(n1) + Sum(A010054(a(k)): 0 <= k < n), see also A097602, A131073.  Reinhard Zumkeller, Nov 15 2012
Also number of distinct sums of 1 through n where each of those can be + or . E.g., {1+2,12,1+2,12} = {3,1,1,3} and a(2) = 4.  Toby Gottfried, Nov 17 2011
This sequence is complete because the sum of the first n terms is always greater or equal to a(n+1)1. Consequently, any nonnegative number can be written as a sum of distinct terms of this sequence. See A204009, A072638.  Frank M Jackson, Jan 09 2012
The sequence is the number of distinct sums of subsets of the nonnegative integers, and its first differences are the positive integers. See A208531 for similar results for the squares.  John W. Layman, Feb 28 2012
a(n) = A014132(n,1) for n > 0.  Reinhard Zumkeller, Dec 12 2012
Apparently the number of Dyck paths of semilength n+1 in which the sum of the first and second ascents add to n+1.  David Scambler, Apr 22 2013
Without 1 and 2, a(n) equals the terminus of the nth partial sum of sequence 1,1,2. Explanation: 1st partial sums of 1,1,2 are 1,2,4; 2nd partial sums are 1,3,7; 3rd partial sums are 1,4,11; 4th partial sums are 1,5,16, etc.  Bob Selcoe, Jul 04 2013
a(n) = A228074(n+1,n).  Reinhard Zumkeller, Aug 15 2013
For n>3, a(n) is the number of length n binary words that have at least two 1's and at most two 0's. a(4) = 11 because we have: 0011, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111.  Geoffrey Critzer, Jan 08 2014
For n > 0: A228446(a(n)) = 3.  Reinhard Zumkeller, Mar 12 2014
Equivalently, numbers of the form 2*m^2+m+1, where m = 0, 1, 1, 2, 2, 3, 3, ... .  Bruno Berselli, Apr 08 2014
For n >= 2: quasitriangular numbers; the almosttriangular numbers being A000096(n), n >= 2. Note that 2 is simultaneously almosttriangular and quasitriangular.  Daniel Forgues, Apr 21 2015
n points in general position determine "n choose 2" lines, so A055503(n) <= a(n(n1)/2). If n > 3, the lines are not in general position and so A055503(n) < a(n(n1)/2).  Jonathan Sondow, Dec 01 2015


REFERENCES

R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
L. Hogben, Choice and Chance by Cardpack and Chessboard. Vol. 1, Chanticleer Press, NY, 1950, p. 22.
Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83. [Robert G. Wilson v, May 21 2010]
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence  see "List of Sequences" in Vol. 2.
A. M. Robert, A Course in padic Analysis, SpringerVerlag, 2000; p. 213.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On singledeletioncorrecting codes, in Codes and Designs (Columbus, OH, 2000), 273291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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, #44 (First published: San Francisco: HoldenDay, Inc., 1964)


LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
J.L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
J.L. Baril, T. Mansour, A. Petrossian, Equivalence classes of permutations modulo excedances, 2014.
JeanLuc Baril and Armen Petrossian, Equivalence classes of permutations modulo descents and lefttoright maxima, preprint, 2015.
A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.
H. Bottomley, Illustration of initial terms
A. Burstein and T. Mansour, Words restricted by 3letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
A. Burstein and T. Mansour, Words restricted by 3letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 114.
David Coles, Triangle Puzzle.
K. Dilcher, K. B. Stolarsky, Nonlinear recurrences related to Chebyshev polynomials, The Ramanujan Journal, 2014, Online Oct. 2014, pp. 123. See Cor. 5.
GuoNiu Han, Enumeration of Standard Puzzles [Cached copy]
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 20132015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 386 [broken link?]
Milan Janjic, Two Enumerative Functions
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.
KyuHwan Lee, Sejin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on kary Heaps, Slides of Talk, 2014.
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292298.
Jim Loy, Triangle Puzzle
T. Mansour, Permutations avoiding a set of patterns from S_3 and a pattern from S_4, arXiv:math/9909019 [math.CO], 1999.
J. W. Meijer and M. Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No.1, December 2008. pp. 176187.
Markus Moll, On a family of random noble means substitutions, Dr. Math. Dissertation, Universität Bielefeld, 2013.
Markus Moll, On a family of random noble means substitutions, arXiv:1312.5136 [math.DS], 2013.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.
D. J. Price, Some unusual series occurring in ndimensional geometry, Math. Gaz., 30 (1946), 149150.
L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, 2014.
N. Reading, On the structure of Bruhat Order, Ph.D. dissertation, University of Minnesota, April 2002.
N. Reading, Order Dimension, Strong Bruhat Order and Lattice Properties for Posets
N. Reading, Order Dimension, Strong Bruhat Order and Lattice Properties for Posets, Order, Vol. 19, no. 1 (2002), 73100.
H. P. Robinson, Letter to N. J. A. Sloane, Aug 16 1971, with attachments
R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383406, 1985; see Example 3.5.
N. J. A. Sloane, On singledeletioncorrecting codes
A. J. Turner, J. F. Miller, Recurrent Cartesian Genetic Programming Applied to Famous Mathematical Sequences, 2014.
Eric Weisstein's World of Mathematics, Circle Division by Lines
Eric Weisstein's World of Mathematics, Plane Division by Lines
Thomas Wieder, The number of certain kcombinations of an nset, Applied Mathematics Electronic Notes, vol. 8 (2008).
Wikipedia, Floyd's triangle [Paul Muljadi, Jan 25 2010]
Index entries for "core" sequences
Index entries for sequences related to centered polygonal numbers
Index entries for linear recurrences with constant coefficients, signature (3,3,1).


FORMULA

G.f.: (1x+x^2)/(1x)^3.
G.f.: (1x^6)/((1x)^2*(1x^2)*(1x^3)). a(n) = a(1n) for all n in Z.  Michael Somos, Sep 04 2006
Euler transform of length 6 sequence [ 2, 1, 1, 0, 0, 1].  Michael Somos, Sep 04 2006
a(n+3) = 3*a(n+2)3*a(n+1)+a(n) and a(1) = 1, a(2) = 2, a(3) = 4.  Artur Jasinski, Oct 21 2008
a(n) = A000217(n) + 1.
a(n) = a(n1)+n. E.g.f.:(1+x+x^2/2)*exp(x).  Geoffrey Critzer, Mar 10 2009
a(n) = sum(k=0..n+1, binomial(n+1, 2(kn))).  Paul Barry, Aug 29 2004
Binomial(n+2,1)2*binomial(n+1,1)+binomial(n+2,2).  Zerinvary Lajos, May 12 2006
a(n) = A086601(n)^(1/2).  Zerinvary Lajos, Apr 25 2008
From Thomas Wieder, Feb 25 2009: (Start)
a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..ni}...Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n) where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i != l_(i+1) and l_(i+1) != 0 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. (End)
a(n) = A034856(n+1)  A005843(n) = A000217(n) + A005408(n)  A005843(n).  Jaroslav Krizek, Sep 05 2009
a(n) = 2*a(n1)a(n2)+1.  Eric Werley, Jun 27 2011
E.g.f.: exp(x)*(1+x+(x^2)/2) = Q(0); Q(k) = 1+x/(1x/(2+x4/(2+x*(k+1)/Q(k+1)))); (continued fraction).  Sergei N. Gladkovskii, Nov 21 2011
a(n) = 1 + floor(n/2) + ceiling(n^2/2) = 1 + A004526(n) + A000982(n).  Wesley Ivan Hurt, Jun 14 2013
a(n) >= A263883(n) and a(n(n1)/2) >= A055503(n).  Jonathan Sondow, Dec 01 2015


EXAMPLE

a(3) = 7 because the 132 and 321avoiding permutations of {1,2,3,4} are 1234, 2134, 3124, 2314, 4123, 3412, 2341.
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 11*x^4 + 16*x^5 + 22*x^6 + 29*x^7 + ...


MAPLE

A000124 := n> n*(n+1)/2+1;
A000124 :=(1z+z**2)/(z1)**3; # Simon Plouffe in his 1992 dissertation


MATHEMATICA

FoldList[#1 + #2 &, 1, Range@ 50] (* Robert G. Wilson v, Feb 02 2011 *)
Accumulate[Range[0, 60]]+1 (* Harvey P. Dale, Mar 12 2013 *)
Select[Range[2000], IntegerQ[Sqrt[8 #  7]] &] (* Vincenzo Librandi, Apr 16 2014 *)


PROG

(PARI) {a(n) = (n^2 + n) / 2 + 1}; /* Michael Somos, Sep 04 2006 */
(Haskell)
a000124 = (+ 1) . a000217
 Reinhard Zumkeller, Oct 04 2012, Nov 15 2011
(MAGMA) [n: n in [0..1500]  IsSquare(8*n7)]; // Vincenzo Librandi, Apr 16 2014


CROSSREFS

Cf. A000096 Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1.
Cf. A002061, A002522, A016028, A055503, A072863, A144328, A177862, A263883.
Slicing a cake: A000125, a bagel: A003600.
Partial sums =(A033547)/2, (A014206)/2.
The first 20 terms are also found in A025732 and A025739.
Cf. A000125, A000127, A002522, A005408, A006261, A016813, A058331, A080856, A086514, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A161711, A161712, A161713, A161715, A014206, A051601.
Cf. A055469 Quasitriangular primes.
Sequence in context: A025732 A025739 * A152947 A212369 A212368 A217838
Adjacent sequences: A000121 A000122 A000123 * A000125 A000126 A000127


KEYWORD

nonn,core,easy,nice,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



