A005285 Number of permutations of (1,...,n) having n-7 inversions (n>=7).
1, 7, 35, 155, 649, 2640, 10569, 41926, 165425, 650658, 2554607, 10020277, 39287173, 154022930, 603919164, 2368601685, 9293159292, 36476745510, 143239635450, 562744102479, 2211876507387, 8697839966552, 34218338900591
Offset: 7
Keywords
Examples
a(8)=7 because we have 21345678, 13245678, 12435678, 12354678, 12346578, 12345768, and 12345687.
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 = 7..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+7,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-7}],{n,7,25}] (* Vaclav Kotesovec, Mar 16 2014 *)
Formula
a(n) = 2^(2*n-8)/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