A000096 a(n) = n*(n+3)/2.

0, 2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135, 152, 170, 189, 209, 230, 252, 275, 299, 324, 350, 377, 405, 434, 464, 495, 527, 560, 594, 629, 665, 702, 740, 779, 819, 860, 902, 945, 989, 1034, 1080, 1127, 1175, 1224, 1274, 1325, 1377, 1430, 1484, 1539, 1595, 1652, 1710, 1769

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

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

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).

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

For n > 3, a(n-3) = dimension of the traveling salesman polytope T(n). - Benoit Cloitre, Aug 18 2002

Also counts quasi-dominoes (quasi-2-ominoes) on an n X n board. Cf. A094170-A094172. - Jon Wild, May 07 2004

Coefficient of x^2 in (1 + x + 2*x^2)^n. - Michael Somos, May 26 2004

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

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

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

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

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

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

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

The only primes are a(1) = 2 and a(2) = 5. - Reinhard Zumkeller, Jul 18 2011

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

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

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

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

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

Numbers k such that 8k + 9 is a square. - Juri-Stepan Gerasimov, Apr 05 2016

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

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

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

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

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

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

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

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

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

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

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

Examples

			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 + ...
		

References

• 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.
• Norman Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993.
• 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. G. Kendall et al., Shape and Shape Theory, Wiley, 1999; see p. 4.
• 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).

Links

• Franklin T. Adams-Watters, Table of n, a(n) for n = 0..10000
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
• D. Applegate, R. Bixby, V. Chvatal and W. Cook, On the solution of traveling salesman problem, In : Int. Congress of mathematics (Berlin 1998), Documenta Math., Extra Volume ICM 1998, Vol. III, pp. 645-656.
• J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
• Robert Davis and Greg Simay, Further Combinatorics and Applications of Two-Toned Tilings, arXiv:2001.11089 [math.CO], 2020.
• L. Euler, Sur une contradiction apparente dans la doctrine des lignes courbes, 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.
• Mareike Fischer, Extremal values of the Sackin balance index for rooted binary trees, arXiv:1801.10418 [q-bio.PE], 2018.
• Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Theorem 1.
• A. Hanson and J. Sha, A Contour Integral Representation for the Dual Five-Point Function and a Symmetry of the Genus Four Surface in R6, arXiv preprint arXiv:0510064 [math-ph], 2005.
• F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), no. 3, 231-243.
• S. P. Humphries, Home page
• S. P. Humphries, Braid groups, infinite Lie algebras of Cartan type and rings of invariants, Topology and its Applications, 95 (3) (1999) pp. 173-205.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1018 [dead link]
• Milan Janjic, Two Enumerative Functions
• Christian Kassel and Christophe Reutenauer, Pairs of intertwined integer sequences, arXiv:2507.15780 [math.NT], 2025. See p. 13.
• A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80 (No. 1, 2007), 29-37.
• Yashar Memarian, On the Maximum Number of Vertices of Minimal Embedded Graphs, arXiv:0910.2469 [math.CO], 2009-15. [_Jonathan Vos Post_, Oct 14 2009]
• Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.
• E. Pérez Herrero, Binomial Matrix (I), Psychedelic Geometry Blogspot 09/22/09. [_Enrique Pérez Herrero_, Sep 22 2009]
• T. Manneville and V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015.
• P. Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
• P. Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• Maria J. Rodriguez, Black holes in all, The KIAS Newsletter, Vol.3, pp.29-34, Korea Institute for Advanced Study, Dec. 2010. [Wayback archive]
• C. Rossiter, Depictions, Explorations and Formulas of the Euler/Pascal Cube. [Wayback archive]
• E. Sandifer, How Euler Did It: Cramer's Paradox, 2004.
• N. J. A. Sloane, How to cut an annulus into 9 pieces with three cuts.
• Ben Sparks and Brady Haran, The Math of Being a Greedy Pig, Numberphile video, 2021.
• Eric Weisstein's World of Mathematics, Cramer-Euler Paradox
• Eric Weisstein's World of Mathematics, Irredundant Set
• Eric Weisstein's World of Mathematics, Path Complement Graph
• G. G. Wojnar, D. Sz. Wojnar, and L. Q. Brin, Universal Peculiar Linear Mean Relationships in All Polynomials, arXiv:1706.08381 [math.GM], 2017.
• Index entries for two-way infinite sequences
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

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

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.

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

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

Similar sequences are listed in A316466.

Cf. A033282, A111785, A126216, A133437.

Programs

GAP

a := List([0..1000], n -> n*(n+3)/2); # Muniru A Asiru, Jan 25 2018

Haskell

a000096 n = n * (n + 3) `div` 2
a000096_list = [x | x <- [0..], a023531 x == 1]
-- Reinhard Zumkeller, Feb 14 2015, Dec 04 2012

Magma

[n*(n+3)/2: n in [0..60]]; // Juri-Stepan Gerasimov, Apr 05 2016

Magma

[n: n in [0..2300] | IsSquare(8*n+9)]; // Juri-Stepan Gerasimov, Apr 05 2016

Maple

A000096 := n->n*(n+3)/2; seq(A000096(n), n=0..50);
A000096 :=z*(-2+z)/(z-1)**3; # Simon Plouffe in his 1992 dissertation

Mathematica

Table[n*(n+3)/2, {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)
LinearRecurrence[{3,-3,1}, {0,2,5}, 60] (* Harvey P. Dale, Apr 30 2013 *)

PARI

{a(n) = n * (n+3)/2}; \\ Michael Somos, May 26 2004

PARI

first(n) = Vec(x*(2-x)/(1-x)^3 + O(x^n), -n) \\ Iain Fox, Dec 12 2017

Formula

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

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

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

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

a(-3-n) = a(n). - Michael Somos, May 26 2004

2*a(n) = A008778(n) - A105163(n). - Creighton Dement, Apr 15 2005

a(n) = C(3+n, 2) - C(3+n, 1). - Zerinvary Lajos, Dec 09 2005

a(n) = A067550(n+1) / A067550(n). - Alexander Adamchuk, May 20 2006

a(n) = A126890(n,1) for n > 0. - Reinhard Zumkeller, Dec 30 2006

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - Paul Curtz, Jan 02 2008

Starting (2, 5, 9, 14, ...) = binomial transform of (2, 3, 1, 0, 0, 0, ...). - Gary W. Adamson, Jul 03 2008

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

A002262(a(n)) = n. - Reinhard Zumkeller, May 20 2009

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

a(n) = Sum_{k=1..n} (k+1)!/k!. - Gary Detlefs, Aug 03 2010

a(n) = n(n+1)/2 + n = A000217(n) + n. - Zak Seidov, Jan 22 2012

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

a(n) = binomial(n+3, 2) - (n+3). - Robert G. Wilson v, Mar 15 2012

a(n) = A181971(n+1, 2) for n > 0. - Reinhard Zumkeller, Jul 09 2012

a(n) = A214292(n+2, 1). - Reinhard Zumkeller, Jul 12 2012

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

A023532(a(n)) = 0. - Reinhard Zumkeller, Dec 04 2012

a(n) = A014132(n,n) for n > 0. - Reinhard Zumkeller, Dec 12 2012

a(n-1) = (1/n!)*Sum_{j=0..n} binomial(n,j)*(-1)^(n-j)*j^n*(j-1). - Vladimir Kruchinin, Jun 06 2013

a(n) = 2n - floor(n/2) + floor(n^2/2). - Wesley Ivan Hurt, Jun 15 2013

a(n) = Sum_{i=2..n+1} i. - Wesley Ivan Hurt, Jun 28 2013

Sum_{n>0} 1/a(n) = 11/9. - Enrique Pérez Herrero, Nov 26 2013

a(n) = Sum_{i=1..n} (n - i + 2). - Wesley Ivan Hurt, Mar 31 2014

A023531(a(n)) = 1. - Reinhard Zumkeller, Feb 14 2015

For n > 0: a(n) = A101881(2*n-1). - Reinhard Zumkeller, Feb 20 2015

a(n) + a(n-1) = A008865(n+1) for all n in Z. - Michael Somos, Nov 11 2015

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

a(n) = (n+1)^2 - A000124(n). - Anton Zakharov, Jun 29 2016

Dirichlet g.f.: (zeta(s-2) + 3*zeta(s-1))/2. - Ilya Gutkovskiy, Jun 30 2016

a(n) = 2*A000290(n+3) - 3*A000217(n+3). - J. M. Bergot, Apr 04 2018

a(n) = Stirling2(n+2, n+1) - 1. - Peter Luschny, Jan 05 2021

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

From Amiram Eldar, Jan 20 2021: (Start)

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

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

Product_{n>=0} a(4*n+1)*a(4*n+4)/(a(4*n+2)*a(4*n+3)) = Pi/6. - Michael Jodl, Apr 05 2025