A001894 Number of permutations of {1,...,n} having n-4 inversions (n>=4).
1, 4, 14, 49, 174, 628, 2298, 8504, 31758, 119483, 452284, 1720774, 6574987, 25214332, 96997223, 374153699, 1446677555, 5605337934, 21758936146, 84604366100, 329453055975, 1284626463105, 5015200610785, 19601107218591, 76685359017750, 300294650988857, 1176939165980809
Offset: 4
Keywords
Examples
a(5)=4 because we have 21345, 13245, 12435, and 12354.
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.
- 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 = 4..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-4), n=4..40); # Barbara Haas Margolius, May 31 2001
-
Mathematica
Table[SeriesCoefficient[Product[(1-x^j)/(1-x),{j,1,n}],{x,0,n-4}],{n,4,25}] (* Vaclav Kotesovec, Mar 16 2014 *)
Formula
a(n) = 2^(2*n-5)/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