A001892 Number of permutations of (1,...,n) having n-2 inversions (n>=2).
1, 2, 5, 15, 49, 169, 602, 2191, 8095, 30239, 113906, 431886, 1646177, 6301715, 24210652, 93299841, 360490592, 1396030396, 5417028610, 21056764914, 81978913225, 319610939055, 1247641114021, 4875896455975, 19075294462185, 74696636715792, 292758662041150
Offset: 2
Keywords
Examples
a(4)=5 because we have 1342, 1423, 2143, 2314, and 3124.
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.
- 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 = 2..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-2), n=2..40);
-
Mathematica
Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-2}],{n,2,25}] (* Vaclav Kotesovec, Mar 16 2014 *)
Formula
a(n) = 2^(2*n-3)/sqrt(Pi*n)*Q*(1+O(n^{-1})), where Q is a digital search tree constant, Q = 0.288788095... (see A048651). - corrected by Vaclav Kotesovec, Mar 16 2014
Extensions
More terms, Maple code, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
Definition clarified by Emeric Deutsch, Aug 02 2014
Comments