A002817 Doubly triangular numbers: a(n) = n*(n+1)*(n^2+n+2)/8.

0, 1, 6, 21, 55, 120, 231, 406, 666, 1035, 1540, 2211, 3081, 4186, 5565, 7260, 9316, 11781, 14706, 18145, 22155, 26796, 32131, 38226, 45150, 52975, 61776, 71631, 82621, 94830, 108345, 123256, 139656, 157641, 177310, 198765, 222111, 247456, 274911, 304590

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Number of inequivalent ways to color vertices of a square using <= n colors, allowing rotations and reflections. Group is dihedral group D_8 of order 8 with cycle index (1/8)*(x1^4 + 2*x4 + 3*x2^2 + 2*x1^2*x2); setting all x_i = n gives the formula a(n) = (1/8)*(n^4 + 2*n + 3*n^2 + 2*n^3).

Number of semi-magic 3 X 3 squares with a line sum of n-1. That is, 3 X 3 matrices of nonnegative integers such that row sums and column sums are all equal to n-1. - [Gupta, 1968, page 653; Bell, 1970, page 279]. - Peter Bertok (peter(AT)bertok.com), Jan 12 2002. See A005045 for another version.

Also the coefficient h_2 of x^{n-3} in the shelling polynomial h(x)=h_0*x^n-1 + h_1*x^n-2 + h_2*x^n-3 + ... + h_n-1 for the independence complex of the cycle matroid of the complete graph K_n on n vertices (n>=2) - Woong Kook (andrewk(AT)math.uri.edu), Nov 01 2006

If X is an n-set and Y a fixed 3-subset of X then a(n-4) is equal to the number of 5-subsets of X intersecting Y. - Milan Janjic, Jul 30 2007

Starting with offset 1 = binomial transform of [1, 5, 10, 9, 3, 0, 0, 0, ...]. - Gary W. Adamson, Aug 05 2009

Starting with "1" = row sums of triangle A178238. - Gary W. Adamson, May 23 2010

The equation n*(n+1)*(n^2 + n + 2)/8 may be arrived at by solving for x in the following equality: (n^2+n)/2 = (sqrt(8x+1)-1)/2. - William A. Tedeschi, Aug 18 2010

Partial sums of A006003. - Jeremy Gardiner, Jun 23 2013

Doubly triangular numbers are revealed in the sums of row sums of Floyd's triangle.

1, 1+5, 1+5+15, ...

1

2 3

4 5 6

7 8 9 10

11 12 13 14 15

- Tony Foster III, Nov 14 2015

From Jaroslav Krizek, Mar 04 2017: (Start)

For n>=1; a(n) = sum of the different sums of elements of all the nonempty subsets of the sets of numbers from 1 to n.

Example: for n = 6; nonempty subsets of the set of numbers from 1 to 3: {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}; sums of elements of these subsets: 1, 2, 3, 3, 4, 5, 6; different sums of elements of these subsets: 1, 2, 3, 4, 5, 6; a(3) = (1+2+3+4+5+6) = 21, ... (End)

a(n) is also the number of 4-cycles in the (n+4)-path complement graph. - Eric W. Weisstein, Apr 11 2018

Examples

			G.f. = x + 6*x^2 + 21*x^3 + 55*x^4 + 120*x^5 + 231*x^6 + 406*x^7 + 666*x^8 + ...
		

References

• A. Björner, The homology and shellability of matroids and geometric lattices, in Matroid Applications (ed. N. White), Encyclopedia of Mathematics and Its Applications, 40, Cambridge Univ. Press 1992.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 124, #25, Q(3,r).
• 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).
• R. P. Stanley, Enumerative Combinatorics I, p. 292.

Links

• T. D. Noe and William A. Tedeschi, Table of n, a(n) for n = 0..10000 (first 1000 terms computed by T. D. Noe)
• G. E. Andrews, P. Paule, A. Riese and V. Strehl, MacMahon's partition analysis V. Bijections, recursions and magic squares, p. 37.
• Weymar Astaiza, Alexander J. Barrios, Henry Chimal-Dzul, Stephan Ramon Garcia, Jaaziel de la Luz, Victor H. Moll, Yunied Puig, and Diego Villamizar, Symmetric tensor powers of graphs, arXiv:2309.13741 [math.CO], 2023. See p. 12.
• Matthias Beck, The number of "magic" squares and hypercubes, arXiv:math/0201013 [math.CO], 2002-2005.
• A. G. Bell, Partitioning integers in n dimensions, The Computer Journal, 13 (1970), 278-283.
• Miklos Bona, A New Proof of the Formula for the Number of 3 X 3 Magic Squares, Mathematics Magazine, Vol. 70, No. 3 (Jun., 1997), pp. 201-203.
• L. Carlitz, Enumeration of symmetric arrays, Duke Math. J., Vol. 33(4) (1966), pp. 771-782.
• Brian Conrey and Alex Gamburd, Pseudomoments of the Riemann zeta-function and pseudomagic squares, Journal of Number Theory, Volume 117, Issue 2, April 2006, Pages 263-278. See H4 on p. 269.
• P. Diaconis and A. Gamburd, Random matrices, magic squares and matching polynomials, Volume 11, Issue 2 (2004-6) (The Stanley Festschrift volume), Research Paper #R2.
• Robert W. Donley, Partitions for semi-magic squares of size three, arXiv:1911.00977 [math.CO], 2019.
• I. J. Good, On the application of symmetric Dirichlet distributions and their mixtures to contingency tables, Ann. Statist. 4 (1976), no. 6, 1159-1189.
• I. J. Good, On the application of symmetric Dirichlet distributions and contingency tables, pp. 1178-1179. (Annotated scanned copy)
• Hansraj Gupta, Enumeration of symmetric matrices, Duke Math. J. 35 (3), 653-659, (September 1968).
• D. M. Jackson and G. H. J. van Rees, The enumeration of generalized double stochastic nonnegative integer square matrices, SIAM J. Comput., 4 (1975), 474-477.
• D. M. Jackson & G. H. J. van Rees, The enumeration of generalized double stochastic nonnegative integer square matrices, SIAM J. Comput., 4.4 (1975), 474-477. (Annotated scanned copy)
• Milan Janjic, Two Enumerative Functions
• Neven Juric, Illustration of the 55 3 X 3 matrices
• Michal Opler, Pavel Valtr, and Tung Anh Vu, On the Arrangement of Hyperplanes Determined by n Points, EuroCG (39th European Workshop on Computational Geometry, Barcelona, Spain 2023) Session 7B, Talk 1, Vol. 54, No. 6.
• 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
• Henry Warburton, On Self-Repeating Series, Transactions of the Cambridge Philosophical Society, Vol. 9, 471-486, 1856.
• Eric Weisstein's World of Mathematics, Graph Cycle
• Eric Weisstein's World of Mathematics, Path Complement Graph
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Cf. A006003 (first differences), A165211 (mod 2).

Multiple triangular: A000217, A064322, A066370.

Cf. A001496, A001621, A178238, A005045, A002721.

Cf. A006528 (square colorings).

Cf. A236770 (see crossrefs).

Cf. A016754, A007204.

Row n=3 of A257493 and row n=2 of A331436 and A343097.

Cf. A000332.

Cf. A000292 (3-cycle count of \bar P_{n+4}), A060446 (5-cycle count of \bar P_{n+3}), A302695 (6-cycle count of \bar P_{n+5}).

Programs

Maple

A002817 := n->n*(n+1)*(n^2+n+2)/8;

Mathematica

a[ n_] := n (n + 1) (n^2 + n + 2) / 8; (* Michael Somos, Jul 24 2002 *)
LinearRecurrence[{5,-10,10,-5,1}, {0,1,6,21,55},40] (* Harvey P. Dale, Jul 18 2011 *)
nn=50;Join[{0},With[{c=(n(n+1))/2},Flatten[Table[Take[Accumulate[Range[ (nn(nn+1))/2]], {c,c}],{n,nn}]]]] (* Harvey P. Dale, Mar 19 2013 *)

PARI

{a(n) = n * (n+1) * (n^2 + n + 2) / 8}; /* Michael Somos, Jul 24 2002 */

PARI

concat(0, Vec(x*(1+x+x^2)/(1-x)^5 + O(x^50))) \\ Altug Alkan, Nov 15 2015

Python

def A002817(n): return (m:=n*(n+1))*(m+2)>>3 # Chai Wah Wu, Aug 30 2024

Formula

a(n) = 3*binomial(n+2, 4) + binomial(n+1, 2).

G.f.: x*(1 + x + x^2)/(1-x)^5. - Simon Plouffe (in his 1992 dissertation); edited by N. J. A. Sloane, May 13 2008

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) + 3. - Warut Roonguthai, Dec 13 1999

a(n) = 5a(n-1) - 10a(n-2) + 10a(n-3) - 5a(n-4) + a(n-5) = A000217(A000217(n)). - Ant King, Nov 18 2010

a(n) = Sum(Sum(1 + Sum(3*n))). - Xavier Acloque, Jan 21 2003

a(n) = A000332(n+1) + A000332(n+2) + A000332(n+3), with A000332(n) = binomial(n, 4). - Mitch Harris, Oct 17 2006 and Bruce J. Nicholson, Oct 22 2017

a(n) = Sum_{i=1..C(n,2)} i = C(C(n,2) + 1, 2) = A000217(A000217(n+1)). - Enrique Pérez Herrero, Jun 11 2012

Euler transform of length 3 sequence [6, 0, -1]. - Michael Somos, Nov 19 2015

E.g.f.: x*(8 + 16*x + 8*x^2 + x^3)*exp(x)/8. - Ilya Gutkovskiy, Apr 26 2016

Sum_{n>=1} 1/a(n) = 6 - 4*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) = 1.25269064911978447... . - Vaclav Kotesovec, Apr 27 2016

a(n) = A000217(n)*A000124(n)/2.

a(n) = ((n-1)^4 + 3*(n-1)^3 + 2*(n-1)^2 + 2*n))/8. - Bruce J. Nicholson, Apr 05 2017

a(n) = (A016754(n)+ A007204(n)- 2) / 32. - Bruce J. Nicholson, Apr 14 2017

a(n) = a(-1-n) for all n in Z. - Michael Somos, Apr 17 2017

a(n) = T(T(n)) where T are the triangular numbers A000217. - Albert Renshaw, Jan 05 2020

a(n) = 2*n^2 - n + 6*binomial(n, 3) + 3*binomial(n, 4). - Ryan Jean, Mar 20 2021

a(n) = (A008514(n) - 1)/16. - Charlie Marion, Dec 20 2024

Extensions

More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Dec 29 1999