|
%I M3894 #60 Sep 08 2022 08:44:33
%S 5,20,49,98,174,285,440,649,923,1274,1715,2260,2924,3723,4674,5795,
%T 7105,8624,10373,12374,14650,17225,20124,23373,26999,31030,35495,
%U 40424,45848,51799,58310,65415,73149,81548,90649,100490,111110,122549,134848,148049
%N Number of permutations of [n] with four inversions.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 255, #2, b(n,4).
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
%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 Vincenzo Librandi, <a href="/A005287/b005287.txt">Table of n, a(n) for n = 4..10000</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_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1).
%F a(n) = n*(n+1)*(n^2+n-14)/24.
%F G.f.: x^4*(-5 + 5*x + x^2 - 3*x^3 + x^4) / (x-1)^5. - _Simon Plouffe_ in his 1992 dissertation
%F binomial(n,4) + binomial(n,3) - binomial(n,2), n>=5. - _Zerinvary Lajos_, Jul 23 2006
%e [2, 4, 3, 1], [3, 2, 4, 1], [3, 4, 1, 2], [4, 1, 3, 2], [4, 2, 1, 3] have 4 inversions.
%p [seq(binomial(n,4)+binomial(n,3)-binomial(n,2), n=5..43)]; # _Zerinvary Lajos_, Jul 23 2006
%t CoefficientList[Series[(z^4 - 3*z^3 + z^2 + 5*z - 5)/(z - 1)^5, {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jul 16 2011 *)
%t LinearRecurrence[{5,-10,10,-5,1},{5,20,49,98,174},40] (* _Harvey P. Dale_, Aug 25 2016 *)
%o (PARI) a(n)=if(n<4,0,n*(n+1)*(n^2+n-14)/24)
%o (Magma) [n*(n+1)*(n^2+n-14)/24: n in [4..50]]; // _Vincenzo Librandi_, Jul 17 2011
%Y Cf. A008302, A005286, A005288.
%K nonn,easy
%O 4,1
%A _N. J. A. Sloane_, _Robert G. Wilson v_
|
