|
| |
|
|
A001893
|
|
Number of permutations of (1,...,n) having n-3 inversions (n>=3).
(Formerly M2810 N1132)
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms, asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
|
|
|
STATUS
|
approved
|
| |
|
|