This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000707 Number of permutations of [1,2,...,n] with n-1 inversions. (Formerly M1646 N0644) 14
 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, 141376666307608 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Same as number of submultisets of size n-1 of the multiset with multiplicities [1,2,...,n-1]. - Joerg Arndt, Jan 10 2011. Stated another way, a(n-1) is the number of size n "multisubsets" (see example) of M = {a^1,b^2,c^3,d^4,...,#^n!}. - Geoffrey Critzer, Apr 01 2010, corrected by Jacob Post, Jan 03 2011 For a more general result (taking multisubset of any size) see A008302. - Jacob Post, Jan 03 2011 The number of ordered submultisets is found in A129481; credit for this observation should go to Marko Riedel at math.stackexchange. - J. M. Bergot, Aug 12 2016 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 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 Alois P. Heinz, Table of n, a(n) for n = 1..1000 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, 2nd ed., Teubner, Leipzig, 1st ed., 1901, p. 96. E. Netto, Lehrbuch der Combinatorik, 2nd ed., Teubner, Leipzig, 1st ed., 1901, p. 96. E. Netto, Lehrbuch der Combinatorik, Chapter 4, annotated scanned copy of pages 92-99 only. J. Shallit, Letter to N. J. A. Sloane, Oct 08 1980 FORMULA See A008302 for G.f. a(n) = 2^(2*n-2)/sqrt(Pi*n)*Q*(1+O(n^(-1))), where Q is a digital search tree constant, Q = product(1-1/(2^n),n=1..infinity) = QPochhammer[1/2, 1/2] = 0.288788095... (see A048651), corrected and extended by Vaclav Kotesovec, Mar 16 2014 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}. - Geoffrey Critzer, Apr 01 2010, corrected by Jacob Post, Jan 03 2011 G.f. = x + x^2 + 2*x^3 + 6*x^4 + 20*x^5 + 71*x^6 + 259*x^7 + 961*x^8 + ... MATHEMATICA Table[SeriesCoefficient[ Series[Product[Sum[x^i, {i, 0, k}], {k, 0, n}], {x, 0, 20}], n], {n, 1, 20}] (* Geoffrey Critzer, Apr 01 2010 *) a[ n_] := SeriesCoefficient[ Product[ Sum[ x^i, {i, 0, k}], {k, 0, n}], {x, 0, n}]; (* Michael Somos, Aug 15 2016 *) PROG (PARI) {a(n) = my(v); if( n<1, 0, sum(k=0, n!-1, v = numtoperm(n, k); n-1 == sum(i=1, n-1, sum(j=i+1, n, v[i]>v[j]))))}; /* Michael Somos, Aug 15 2016 */ CROSSREFS One of the diagonals of triangle in A008302. Cf. A048651, A129481. Sequence in context: A151286 A047126 A145138 * A129777 A108600 A274484 Adjacent sequences:  A000704 A000705 A000706 * A000708 A000709 A000710 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS More terms from James A. Sellers, Dec 16 1999 Asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001 Better definition from Joerg Arndt, Jan 10 2011 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 21 09:11 EST 2018. Contains 317431 sequences. (Running on oeis4.)