A005286 a(n) = (n + 3)*(n^2 + 6*n + 2)/6.

1, 6, 15, 29, 49, 76, 111, 155, 209, 274, 351, 441, 545, 664, 799, 951, 1121, 1310, 1519, 1749, 2001, 2276, 2575, 2899, 3249, 3626, 4031, 4465, 4929, 5424, 5951, 6511, 7105, 7734, 8399, 9101, 9841, 10620, 11439, 12299, 13201, 14146, 15135, 16169, 17249

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Number of permutations of [n+3] with three inversions. - Michael Somos, Jun 25 2002

This sequence is related to A241765 by A241765(n) = n*a(n) - Sum_{i=0..n-1} a(i), with A241765(0)=0. For example: A241765(4) = 4*49 - (29+15+6+1) = 145. - Bruno Berselli, Apr 29 2014

For n >= 2, a(n) is also the number of multiplications between two nonzero matrix elements involved in calculating the product of an (n+1) X (n+1) Hessenberg matrix and an (n+1) X (n+1) upper triangular matrix. The formula for n X n matrices is (n+2)(n^2+4n-3)/6 multiplications, n >= 3. - John M. Coffey, Jul 18 2016

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 255, #2, b(n,3).
• R. K. Guy, personal communication.
• E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Exercise 1.30, p. 49.

Links

• T. D. Noe, Table of n, a(n) for n = 0..1000
• R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
• R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
• 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
• Index entries for linear recurrences with constant coefficients, signature (4, -6, 4, -1).

Crossrefs

Cf. A008302, A193106, A193107, A241765.

Programs

Mathematica

Table[(n + 3) (n^2 + 6*n + 2)/6, {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 16 2011 *)
LinearRecurrence[{4,-6,4,-1},{1,6,15,29},50] (* Harvey P. Dale, Mar 07 2012 *)
Table[Binomial[n, 3] + Binomial[n, 2] - n, {n, 3, 47}] (* or *)
CoefficientList[Series[(1 + 2 x - 3 x^2 + x^3)/(1 - x)^4, {x, 0, 44}], x] (* Michael De Vlieger, Jul 09 2016 *)

PARI

a(n)=n+=3; (n^3-7*n)/6 /* Michael Somos, May 12 2005 */

Formula

G.f.: (1+2*x-3*x^2+x^3)/(1-x)^4. - Simon Plouffe in his 1992 dissertation

a(-6-n) = -a(n). - Michael Somos, May 12 2005

a(n) = a(n-1) + A000096(n+1) = A005581(n+2) - 1. - Henry Bottomley, Oct 25 2001

(m^3-7*m)/6 for m >= 3 gives the same sequence. - N. J. A. Sloane, Jul 15 2011

a(0)=1, a(1)=6, a(2)=15, a(3)=29, a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Harvey P. Dale, Mar 07 2012

E.g.f.: (6 + 30*x + 12*x^2 + x^3)*exp(x)/6. - Ilya Gutkovskiy, Jul 09 2016