A000096 - OEIS

%I M1356 N0522 #469 Jun 28 2024 23:20:02

%S 0,2,5,9,14,20,27,35,44,54,65,77,90,104,119,135,152,170,189,209,230,

%T 252,275,299,324,350,377,405,434,464,495,527,560,594,629,665,702,740,

%U 779,819,860,902,945,989,1034,1080,1127,1175,1224,1274,1325,1377,1430,1484,1539,1595,1652,1710,1769

%N a(n) = n*(n+3)/2.

%C For n >= 1, a(n) is the maximal number of pieces that can be obtained by cutting an annulus with n cuts. See illustration. - _Robert G. Wilson v_

%C n(n-3)/2 (n >= 3) is the number of diagonals of an n-gon. - Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr)

%C n(n-3)/2 (n >= 4) is the degree of the third-smallest irreducible presentation of the symmetric group S_n (cf. James and Kerber, Appendix 1).

%C a(n) is also the multiplicity of the eigenvalue (-2) of the triangle graph Delta(n+1). (See p. 19 in Biggs.) - Felix Goldberg (felixg(AT)tx.technion.ac.il), Nov 25 2001

%C For n > 3, a(n-3) = dimension of the traveling salesman polytope T(n). - _Benoit Cloitre_, Aug 18 2002

%C Also counts quasi-dominoes (quasi-2-ominoes) on an n X n board. Cf. A094170-A094172. - _Jon Wild_, May 07 2004

%C Coefficient of x^2 in (1 + x + 2*x^2)^n. - _Michael Somos_, May 26 2004

%C a(n) is the number of "prime" n-dimensional polyominoes. A "prime" n-polyomino cannot be formed by connecting any other n-polyominoes except for the n-monomino and the n-monomino is not prime. E.g., for n=1, the 1-monomino is the line of length 1 and the only "prime" 1-polyominoes are the lines of length 2 and 3. This refers to "free" n-dimensional polyominoes, i.e., that can be rotated along any axis. - Bryan Jacobs (bryanjj(AT)gmail.com), Apr 01 2005

%C Solutions to the quadratic equation q(m, r) = (-3 +- sqrt(9 + 8(m - r))) / 2, where m - r is included in a(n). Let t(m) = the triangular number (A000217) less than some number k and r = k - t(m). If k is neither prime nor a power of two and m - r is included in A000096, then m - q(m, r) will produce a value that shares a divisor with k. - _Andrew S. Plewe_, Jun 18 2005

%C Sum_{k=2..n+1} 4/(k*(k+1)*(k-1)) = ((n+3)*n)/((n+2)*(n+1)). Numerator(Sum_{k=2..n+1} 4/(k*(k+1)*(k-1))) = (n+3)*n/2. - _Alexander Adamchuk_, Apr 11 2006

%C Number of rooted trees with n+3 nodes of valence 1, no nodes of valence 2 and exactly two other nodes. I.e., number of planted trees with n+2 leaves and exactly two branch points. - Theo Johnson-Freyd (theojf(AT)berkeley.edu), Jun 10 2007

%C If X is an n-set and Y a fixed 2-subset of X then a(n-2) is equal to the number of (n-2)-subsets of X intersecting Y. - _Milan Janjic_, Jul 30 2007

%C For n >= 1, a(n) is the number of distinct shuffles of the identity permutation on n+1 letters with the identity permutation on 2 letters (12). - _Camillia Smith Barnes_, Oct 04 2008

%C If s(n) is a sequence defined as s(1) = x, s(n) = kn + s(n-1) + p for n > 1, then s(n) = a(n-1)*k + (n-1)*p + x. - _Gary Detlefs_, Mar 04 2010

%C The only primes are a(1) = 2 and a(2) = 5. - _Reinhard Zumkeller_, Jul 18 2011

%C a(n) = m such that the (m+1)-th triangular number minus the m-th triangular number is the (n+1)-th triangular number: (m+1)(m+2)/2 - m(m+1)/2 = (n+1)(n+2)/2. - _Zak Seidov_, Jan 22 2012

%C For n >= 1, number of different values that Sum_{k=1..n} c(k)*k can take where the c(k) are 0 or 1. - _Joerg Arndt_, Jun 24 2012

%C On an n X n chessboard (n >= 2), the number of possible checkmate positions in the case of king and rook versus a lone king is 0, 16, 40, 72, 112, 160, 216, 280, 352, ..., which is 8*a(n-2). For a 4 X 4 board the number is 40. The number of positions possible was counted including all mirror images and rotations for all four sides of the board. - _Jose Abutal_, Nov 19 2013

%C If k = a(i-1) or k = a(i+1) and n = k + a(i), then C(n, k-1), C(n, k), C(n, k+1) are three consecutive binomial coefficients in arithmetic progression and these are all the solutions. There are no four consecutive binomial coefficients in arithmetic progression. - _Michael Somos_, Nov 11 2015

%C a(n-1) is also the number of independent components of a symmetric traceless tensor of rank 2 and dimension n >= 1. - _Wolfdieter Lang_, Dec 10 2015

%C Numbers k such that 8k + 9 is a square. - _Juri-Stepan Gerasimov_, Apr 05 2016

%C a(n) = (n+1)^2 - A000124(n).- _Anton Zakharov_, Jun 29 2016

%C Let phi_(D,rho) be the average value of a generic degree D monic polynomial f when evaluated at the roots of the rho-th derivative of f, expressed as a polynomial in the averaged symmetric polynomials in the roots of f. [See the Wojnar et al. link] The "last" term of phi_(D,rho) is a multiple of the product of all roots of f; the coefficient is expressible as a polynomial h_D(N) in N:=D-rho. These polynomials are of the form h_D(N)= ((-1)^D/(D-1)!)*(D-N)*N^chi*g_D(N) where chi = (1 if D is odd, 0 if D is even) and g_D(N) is a monic polynomial of degree (D-2-chi). Then a(n) are the negated coefficients of the next to the highest order term in the polynomials N^chi*g_D(N), starting at D=3. - _Gregory Gerard Wojnar_, Jul 19 2017

%C For n >= 2, a(n) is the number of summations required to solve the linear regression of n variables (n-1 independent variables and 1 dependent variable). - _Felipe Pedraza-Oropeza_, Dec 07 2017

%C For n >= 2, a(n) is the number of sums required to solve the linear regression of n variables: 5 for two variables (sums of X, Y, X^2, Y^2, X*Y), 9 for 3 variables (sums of X1, X2, Y1, X1^2, X1*X2, X1*Y, X2^2, X2*Y, Y^2), and so on. - _Felipe Pedraza-Oropeza_, Jan 11 2018

%C a(n) is the area of a triangle with vertices at (n, n+1), ((n+1)*(n+2)/2, (n+2)*(n+3)/2), ((n+2)^2, (n+3)^2). - _J. M. Bergot_, Jan 25 2018

%C Number of terms less than 10^k: 1, 4, 13, 44, 140, 446, 1413, 4471, 14141, 44720, 141420, 447213, ... - _Muniru A Asiru_, Jan 25 2018

%C a(n) is also the number of irredundant sets in the (n+1)-path complement graph for n > 2. - _Eric W. Weisstein_, Apr 11 2018

%C a(n) is also the largest number k such that the largest Dyck path of the symmetric representation of sigma(k) has exactly n peaks, n >= 1. (Cf. A237593.) - _Omar E. Pol_, Sep 04 2018

%C For n > 0, a(n) is the number of facets of associahedra. Cf. A033282 and A126216 and their refinements A111785 and A133437 for related combinatorial and analytic constructs. See p. 40 of Hanson and Sha for a relation to projective spaces and string theory. - _Tom Copeland_, Jan 03 2021

%C For n > 0, a(n) is the number of bipartite graphs with 2n or 2n+1 edges, no isolated vertices, and a stable set of cardinality 2. - _Christian Barrientos_, Jun 13 2022

%C For n >= 2, a(n-2) is the number of permutations in S_n which are the product of two different transpositions of adjacent points. - _Zbigniew Wojciechowski_, Mar 31 2023

%C a(n) represents the optimal stop-number to achieve the highest running score for the Greedy Pig game with an (n-1)-sided die with a loss on a 1. The total at which one should stop is a(s-1),  e.g. for a 6-sided die, one should pass the die at 20. See Sparks and Haran. - _Nicholas Stefan Georgescu_, Jun 09 2024

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), Table 22.7, p. 797.

%D Norman Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993.

%D G. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Maths. and its Appls., Vol. 16, Addison-Wesley, 1981, Reading, MA, U.S.A.

%D D. G. Kendall et al., Shape and Shape Theory, Wiley, 1999; see p. 4.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Franklin T. Adams-Watters, <a href="/A000096/b000096.txt">Table of n, a(n) for n = 0..10000</a>

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H D. Applegate, R. Bixby, V. Chvatal and W. Cook, <a href="https://elibm.org/article/10011619">On the solution of traveling salesman problem</a>, In : Int. Congress of mathematics (Berlin 1998), Documenta Math., Extra Volume ICM 1998, Vol. III, pp. 645-656.

%H J.-L. Baril, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p178">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.

%H Robert Davis and Greg Simay, <a href="https://arxiv.org/abs/2001.11089">Further Combinatorics and Applications of Two-Toned Tilings</a>, arXiv:2001.11089 [math.CO], 2020.

%H L. Euler, <a href="http://eulerarchive.maa.org/pages/E147.html">Sur une contradiction apparente dans la doctrine des lignes courbes</a>, Mémoires de l'Académie des Sciences de Berlin, 4, 219-233, 1750 Reprinted in Opera Omnia, Series I, Vol. 26. pp. 33-45.

%H Mareike Fischer, <a href="https://arxiv.org/abs/1801.10418">Extremal values of the Sackin balance index for rooted binary trees</a>, arXiv:1801.10418 [q-bio.PE], 2018.

%H Mareike Fischer, <a href="https://doi.org/10.1007/s00026-021-00539-2">Extremal Values of the Sackin Tree Balance Index</a>, Ann. Comb. (2021) Vol. 25, 515-541, Theorem 1.

%H A. Hanson and J. Sha, <a href="https://arxiv.org/abs/math-ph/0510064">A Contour Integral Representation for the Dual Five-Point Function and a Symmetry of the Genus Four Surface in R6</a>, arXiv preprint arXiv:0510064 [math-ph], 2005.

%H F. T. Howard and Curtis Cooper, <a href="http://www.fq.math.ca/Papers1/49-3/HowardCooper.pdf">Some identities for r-Fibonacci numbers</a>, Fibonacci Quart. 49 (2011), no. 3, 231-243.

%H S. P. Humphries, <a href="http://www.math.byu.edu/~steve/">Home page</a>

%H S. P. Humphries, <a href="http://dx.doi.org/10.1016/S0166-8641(98)00007-8">Braid groups, infinite Lie algebras of Cartan type and rings of invariants</a>, Topology and its Applications, 95 (3) (1999) pp. 173-205.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1018">Encyclopedia of Combinatorial Structures 1018</a>

%H Milan Janjic, <a href="http://www.pmfbl.org/janjic/">Two Enumerative Functions</a>

%H A. McLeod and W. O. J. Moser, <a href="http://www.jstor.org/stable/27642988">Counting cyclic binary strings</a>, Math. Mag., 80 (No. 1, 2007), 29-37.

%H Yashar Memarian, <a href="http://arxiv.org/abs/0910.2469">On the Maximum Number of Vertices of Minimal Embedded Graphs</a>, arXiv:0910.2469 [math.CO], 2009-15. [_Jonathan Vos Post_, Oct 14 2009]

%H Ângela Mestre and José Agapito, <a href="https://www.emis.de/journals/JIS/VOL22/Agapito/mestre8.html">A Family of Riordan Group Automorphisms</a>, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.

%H E. Pérez Herrero, <a href="http://psychedelic-geometry.blogspot.com/2009/09/binomial-matrix-i.html">Binomial Matrix (I)</a>, Psychedelic Geometry Blogspot 09/22/09. [_Enrique Pérez Herrero_, Sep 22 2009]

%H T. Manneville and V. Pilaud, <a href="http://arxiv.org/abs/1501.07152">Compatibility fans for graphical nested complexes</a>, arXiv preprint arXiv:1501.07152 [math.CO], 2015.

%H P. Moree, <a href="https://arxiv.org/abs/math/0311205">Convoluted convolved Fibonacci numbers</a>, arXiv:math/0311205 [math.CO], 2003.

%H P. Moree, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.htm">Convoluted Convolved Fibonacci Numbers</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Maria J. Rodriguez, <a href="http://www.kias.re.kr/etc_img/bbs_file/KNE_2010/KNE_2010_29.pdf">Black holes in all</a>, The KIAS Newsletter, Vol.3, pp.29-34, Korea Institute for Advanced Study, Dec. 2010.

%H C. Rossiter, <a href="http://noticingnumbers.net/300SeriesCube.htm">Depictions, Explorations and Formulas of the Euler/Pascal Cube</a>.

%H E. Sandifer, <a href="https://www.maa.org/sites/default/files/pdf/editorial/euler/How%20Euler%20Did%20It%2010%20Cramers%20Paradox.pdf">How Euler Did It: Cramer's Paradox</a>

%H N. J. A. Sloane, <a href="/A000096/a000096.pdf">How to cut an annulus into 9 pieces with three cuts.</a>

%H Ben Sparks and Brady Haran, <a href="https://www.youtube.com/watch?v=ULhRLGzoXQ0">The Math of Being a Greedy Pig</a>, Numberphile video, 2021.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cramer-EulerParadox.html">Cramer-Euler Paradox</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IrredundantSet.html">Irredundant Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>

%H G. G. Wojnar, D. Sz. Wojnar, and L. Q. Brin, <a href="http://arxiv.org/abs/1706.08381">Universal Peculiar Linear Mean Relationships in All Polynomials</a>, arXiv:1706.08381 [math.GM], 2017.

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%F G.f.: A(x) = x*(2-x)/(1-x)^3. a(n) = binomial(n+1, n-1) + binomial(n, n-1).

%F Connection with triangular numbers: a(n) = A000217(n+1) - 1.

%F a(n) = a(n-1) + n + 1. - Bryan Jacobs (bryanjj(AT)gmail.com), Apr 01 2005

%F a(n) = 2*t(n) - t(n-1) where t() are the triangular numbers, e.g., a(5) = 2*t(5) - t(4) = 2*15 - 10 = 20. - _Jon Perry_, Jul 23 2003

%F a(-3-n) = a(n). - _Michael Somos_, May 26 2004

%F 2*a(n) = A008778(n) - A105163(n). - _Creighton Dement_, Apr 15 2005

%F a(n) = C(3+n, 2) - C(3+n, 1). - _Zerinvary Lajos_, Dec 09 2005

%F a(n) = A067550(n+1) / A067550(n). - _Alexander Adamchuk_, May 20 2006

%F a(n) = A126890(n,1) for n > 0. - _Reinhard Zumkeller_, Dec 30 2006

%F a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - _Paul Curtz_, Jan 02 2008

%F Starting (2, 5, 9, 14, ...) = binomial transform of (2, 3, 1, 0, 0, 0, ...). - _Gary W. Adamson_, Jul 03 2008

%F For n >= 0, a(n+2) = b(n+1) - b(n), where b(n) is the sequence A005586. - _K.V.Iyer_, Apr 27 2009

%F A002262(a(n)) = n. - _Reinhard Zumkeller_, May 20 2009

%F Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n>=1, a(n-1)=coeff(charpoly(A,x),x^(n-2)). - _Milan Janjic_, Jul 08 2010

%F a(n) = Sum_{k=1..n} (k+1)!/k!. - _Gary Detlefs_, Aug 03 2010

%F a(n) = n(n+1)/2 + n = A000217(n) + n. - _Zak Seidov_, Jan 22 2012

%F E.g.f.: F(x) = 1/2*x*exp(x)*(x+4) satisfies the differential equation F''(x) - 2*F'(x) + F(x) = exp(x). - _Peter Bala_, Mar 14 2012

%F a(n) = binomial(n+3, 2) - (n+3). - _Robert G. Wilson v_, Mar 15 2012

%F a(n) = A181971(n+1, 2) for n > 0. - _Reinhard Zumkeller_, Jul 09 2012

%F a(n) = A214292(n+2, 1). - _Reinhard Zumkeller_, Jul 12 2012

%F G.f.: -U(0) where U(k) = 1 - 1/((1-x)^2 - x*(1-x)^4/(x*(1-x)^2 - 1/U(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Sep 27 2012

%F A023532(a(n)) = 0. - _Reinhard Zumkeller_, Dec 04 2012

%F a(n) = A014132(n,n) for n > 0. - _Reinhard Zumkeller_, Dec 12 2012

%F a(n-1) = (1/n!)*Sum_{j=0..n} binomial(n,j)*(-1)^(n-j)*j^n*(j-1). - _Vladimir Kruchinin_, Jun 06 2013

%F a(n) = 2n - floor(n/2) + floor(n^2/2). - _Wesley Ivan Hurt_, Jun 15 2013

%F a(n) = Sum_{i=2..n+1} i. - _Wesley Ivan Hurt_, Jun 28 2013

%F Sum_{n>0} 1/a(n) = 11/9. - _Enrique Pérez Herrero_, Nov 26 2013

%F a(n) = Sum_{i=1..n} (n - i + 2). - _Wesley Ivan Hurt_, Mar 31 2014

%F A023531(a(n)) = 1. - _Reinhard Zumkeller_, Feb 14 2015

%F For n > 0: a(n) = A101881(2*n-1). - _Reinhard Zumkeller_, Feb 20 2015

%F a(n) + a(n-1) = A008865(n+1) for all n in Z. - _Michael Somos_, Nov 11 2015

%F a(n+1) = A127672(4+n, n), n >= 0, where A127672 gives the coefficients of the Chebyshev C polynomials. See the Abramowitz-Stegun reference. - _Wolfdieter Lang_, Dec 10 2015

%F a(n) = (n+1)^2 - A000124(n). - _Anton Zakharov_, Jun 29 2016

%F Dirichlet g.f.: (zeta(s-2) + 3*zeta(s-1))/2. - _Ilya Gutkovskiy_, Jun 30 2016

%F a(n) = 2*A000290(n+3) - 3*A000217(n+3). - _J. M. Bergot_, Apr 04 2018

%F a(n) = Stirling2(n+2, n+1) - 1. - _Peter Luschny_, Jan 05 2021

%F Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(2)/3 - 5/9. - _Amiram Eldar_, Jan 10 2021

%F From _Amiram Eldar_, Jan 20 2021: (Start)

%F Product_{n>=1} (1 + 1/a(n)) = 3.

%F Product_{n>=1} (1 - 1/a(n)) = 3*cos(sqrt(17)*Pi/2)/(4*Pi). (End)

%e G.f. = 2*x + 5*x^2 + 9*x^3 + 14*x^4 + 20*x^5 + 27*x^6 + 35*x^7 + 44*x^8 + 54*x^9 + ...

%p A000096 := n->n*(n+3)/2; seq(A000096(n), n=0..50);

%p A000096 :=z*(-2+z)/(z-1)**3; # _Simon Plouffe_ in his 1992 dissertation

%t Table[n*(n+3)/2, {n, 0, 100}] (* _Vladimir Joseph Stephan Orlovsky_, Oct 25 2008 *)

%t LinearRecurrence[{3,-3,1}, {0,2,5}, 60] (* _Harvey P. Dale_, Apr 30 2013 *)

%o (PARI) {a(n) = n * (n+3)/2}; \\ _Michael Somos_, May 26 2004

%o (PARI) first(n) = Vec(x*(2-x)/(1-x)^3 + O(x^n), -n) \\ _Iain Fox_, Dec 12 2017

%o (Haskell)

%o a000096 n = n * (n + 3) `div` 2

%o a000096_list = [x | x <- [0..], a023531 x == 1]

%o -- _Reinhard Zumkeller_, Feb 14 2015, Dec 04 2012

%o (Magma) [n*(n+3)/2: n in [0..60]]; or [n: n in [0..2300] | IsSquare(8*n+9)]; // _Juri-Stepan Gerasimov_, Apr 05 2016

%o (GAP) a := List([0..1000], n -> n*(n+3)/2); # _Muniru A Asiru_, Jan 25 2018

%Y Complement of A007401. Column 2 of A145324. Column of triangle A014473, first skew subdiagonal of A033282, a diagonal of A079508.

%Y Occurs as a diagonal in A074079/A074080, i.e., A074079(n+3, n) = A000096(n-1) for all n >= 2. Also A074092(n) = 2^n * A000096(n-1) after n >= 2.

%Y Cf. A000124, A000217, A005581-A005584, A023531, A034856, A067550, A127672 (Chebyshev C).

%Y Cf. numbers of the form n*(n*k-k+4)/2 listed in A226488.

%Y Similar sequences are listed in A316466.

%Y Cf. A033282, A111785, A126216, A133437.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_