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

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,3

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

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

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

Example

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

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

Prog

(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

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

Sequence in context: A238702 A162539 A259474 * A132366 A015641 A292950

Adjacent sequences: A002814 A002815 A002816 * A002818 A002819 A002820

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved