A001893 Number of permutations of (1,...,n) having n-3 inversions (n>=3).
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
Keywords
Examples
a(4)=3 because we have 1243, 1324, and 2134.
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.
Programs
-
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 *)
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
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