A001893 Number of permutations of (1,...,n) having n-3 inversions (n>=3). (Formerly M2810 N1132)

1, 3, 9, 29, 98, 343, 1230, 4489, 16599, 61997, 233389, 884170, 3366951, 12876702, 49424984, 190297064, 734644291, 2842707951, 11022366544, 42815701060, 166583279325, 649063995030, 2532267577126, 9891097066760, 38676401680776, 151381995733542, 593053313030007

Offset

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

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356.

R. K. Guy, personal communication.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 15.

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

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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 = 3..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.

E. Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only.

Formula

a(n) = 2^(2*n-4)/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(4)=3  because we have 1243, 1324, and 2134.

Maple

f := (x, n)->product((1-x^j)/(1-x), j=1..n); seq(coeff(series(f(x, n), x, n+2), x, n-3), n=3..40); # Barbara Haas Margolius, May 31 2001

Mathematica

Table[SeriesCoefficient[Product[(1-x^j)/(1-x), {j, 1, n}], {x, 0, n-3}], {n, 3, 25}] (* Vaclav Kotesovec, Mar 16 2014 *)

Crossrefs

Cf. A008302, A048651.

Sequence in context: A148939 A346158 A077587 * A238979 A151030 A066331

Adjacent sequences: A001890 A001891 A001892 * A001894 A001895 A001896

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