|
| |
|
|
A000707
|
|
Number of permutations of [1,2,...,n] with n-1 inversions.
(Formerly M1646 N0644)
|
|
2
| |
|
|
1, 1, 2, 6, 20, 71, 259, 961, 3606, 13640, 51909, 198497, 762007, 2934764, 11333950, 43874857, 170193528, 661386105, 2574320659, 10034398370, 39163212165, 153027659730, 598577118991, 2343628878849, 9184197395425, 36020235035016
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Same as submultisets of size n-1 of the multiset with multiplicities [1,2,...,n-1]. - Joerg Arndt, Jan 10 2011.
a(n-1) is the number of size n "multisubsets" (see example) of M = {a^1,b^2,c^3,d^4,...,#^n!}. [From Geoffrey Critzer, Apr 01 2010] [corrected by Jacob Post, Jan 03 2011]
For a more general result (taking multisubset of any size) see A008302. [From Jacob Post, Jan 03 2011]
|
|
|
REFERENCES
| F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 15.
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. 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
| B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
|
|
|
FORMULA
| See A008302 for G.f.
a(n)=2^(2*n)/sqrt(pi*n)*Q(1+O(n^(-1))) where Q is a digital search tree constant, Q = 0.2887880951...
|
|
|
EXAMPLE
| a(4) = 6 because there are 6 multisubsets of {a,b,b,c,c,c} with cardinality =3: {a,b,b},{a,b,c},{a,c,c},{b,b,c},{b,c,c},{c,c,c}. [From Geoffrey Critzer, Apr 01 2010] [corrected by Jacob Post, Jan 03 2011]
|
|
|
MATHEMATICA
| Table[SeriesCoefficient[ Series[Product[Sum[x^i, {i, 0, k}], {k, 0, n}], {x, 0, 20}], n], {n, 1, 20}] [From Geoffrey Critzer, Apr 01 2010]
|
|
|
CROSSREFS
| One of the diagonals of triangle in A008302.
Sequence in context: A151286 A047126 A145138 * A129777 A108600 A128729
Adjacent sequences: A000704 A000705 A000706 * A000708 A000709 A000710
|
|
|
KEYWORD
| nonn,nice,easy,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from James A. Sellers (sellersj(AT)math.psu.edu), Dec 16 1999
Asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu) May 31 2001
Better definition from J. Arndt, Jan 10 2011
|
| |
|
|
