A005285 Number of permutations of (1,...,n) having n-7 inversions (n>=7). (Formerly M4414)

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

Comments

Sequence is a diagonal of the triangle A008302 (number of permutations of (1,...,n) with k inversions; see Table 1 of the Margolius reference). - Emeric Deutsch, Aug 02 2014

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.

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

Example

a(8)=7 because we have 21345678, 13245678, 12435678, 12354678, 12346578, 12345768, and 12345687.

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

Crossrefs

Cf. A008302, A000707, A001892, A001893, A001894, A005283, A005284, A048651.

Sequence in context: A370391 A217274 A000588 * A371964 A006095 A171477

Adjacent sequences: A005282 A005283 A005284 * A005286 A005287 A005288

Keyword

nonn

Author

N. J. A. Sloane

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

Status

approved