A005284 Number of permutations of (1,...,n) having n-6 inversions (n>=6).
1, 6, 27, 111, 440, 1717, 6655, 25728, 99412, 384320, 1487262, 5762643, 22357907, 86859412, 337879565, 1315952428, 5131231668, 20029728894, 78265410550, 306109412100, 1198306570554, 4694809541046, 18407850118383
Offset: 6
Keywords
Examples
a(7)=6 because we have 2134567, 1324567, 1243567, 1235467, 1234657 and 1234576.
References
- S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.
- 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).
Links
- G. C. Greubel, Table of n, a(n) for n = 6..1000
- R. K. Guy, Letter to N. J. A. Sloane with attachment, Mar 1988
- B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
- R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag., 61 (1988), 24-29.
Programs
-
Maple
g := proc(n,k) option remember; if k=0 then return(1) else if (n=1 and k=1) then return(0) else if (k<0 or k>binomial(n,2)) then return(0) else g(n-1,k)+g(n,k-1)-g(n-1,k-n) end if end if end if end proc; seq(g(j+6,j),j=0..30); # Barbara Haas Margolius, May 31 2001
-
Mathematica
Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-6}],{n,6,25}] (* Vaclav Kotesovec, Mar 16 2014 *)
Formula
a(n) = 2^(2*n-7)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.2887880951... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014
Extensions
More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
Definition clarified by Emeric Deutsch, Aug 02 2014
Comments