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

%I M4109 #81 Apr 13 2022 13:25:17

%S 1,6,15,29,49,76,111,155,209,274,351,441,545,664,799,951,1121,1310,

%T 1519,1749,2001,2276,2575,2899,3249,3626,4031,4465,4929,5424,5951,

%U 6511,7105,7734,8399,9101,9841,10620,11439,12299,13201,14146,15135,16169,17249

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

%C Number of permutations of [n+3] with three inversions. - _Michael Somos_, Jun 25 2002

%C 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

%C 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

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 255, #2, b(n,3).

%D R. K. Guy, personal communication.

%D E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Exercise 1.30, p. 49.

%H T. D. Noe, <a href="/A005286/b005286.txt">Table of n, a(n) for n = 0..1000</a>

%H R. K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>

%H R. H. Moritz and R. C. Williams, <a href="http://www.jstor.org/stable/2690326">A coin-tossing problem and some related combinatorics</a>, Math. Mag., 61 (1988), 24-29.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4, -6, 4, -1).

%F G.f.: (1+2*x-3*x^2+x^3)/(1-x)^4. - _Simon Plouffe_ in his 1992 dissertation

%F a(-6-n) = -a(n). - _Michael Somos_, May 12 2005

%F a(n) = a(n-1) + A000096(n+1) = A005581(n+2) - 1. - _Henry Bottomley_, Oct 25 2001

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

%F 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

%F E.g.f.: (6 + 30*x + 12*x^2 + x^3)*exp(x)/6. - _Ilya Gutkovskiy_, Jul 09 2016

%t Table[(n + 3) (n^2 + 6*n + 2)/6, {n, 0, 100}] (* _Vladimir Joseph Stephan Orlovsky_, Jul 16 2011 *)

%t LinearRecurrence[{4,-6,4,-1},{1,6,15,29},50] (* _Harvey P. Dale_, Mar 07 2012 *)

%t Table[Binomial[n, 3] + Binomial[n, 2] - n, {n, 3, 47}] (* or *)

%t CoefficientList[Series[(1 + 2 x - 3 x^2 + x^3)/(1 - x)^4, {x, 0, 44}], x] (* _Michael De Vlieger_, Jul 09 2016 *)

%o (PARI) a(n)=n+=3; (n^3-7*n)/6 /* _Michael Somos_, May 12 2005 */

%Y Cf. A008302, A193106, A193107, A241765.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_