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

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

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

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

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

Prog

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

Crossrefs

Cf. A008302, A193106, A193107, A241765.

Sequence in context: A365418 A180953 A200184 * A298877 A229063 A025212

Adjacent sequences: A005283 A005284 A005285 * A005287 A005288 A005289

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved