|
%I M1646 N0644 #93 Jun 26 2023 10:36:34
%S 1,1,2,6,20,71,259,961,3606,13640,51909,198497,762007,2934764,
%T 11333950,43874857,170193528,661386105,2574320659,10034398370,
%U 39163212165,153027659730,598577118991,2343628878849,9184197395425,36020235035016,141376666307608
%N Number of permutations of [1,2,...,n] with n-1 inversions.
%C 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
%C For a more general result (taking multisubset of any size) see A008302. - _Jacob Post_, Jan 03 2011
%C The number of ordered submultisets is found in A129481; credit for this observation should go to Marko Riedel at Mathematics Stack Exchange (see link). - _J. M. Bergot_, Aug 12 2016
%C The number of ordered submultisets is found in A129481. - _J. M. Bergot_, Aug 12 2016
%C For n>0: a(n) is the number of compositions of n-1 into n-1 nonnegative parts such that the i-th part is not larger than i. a(4) = 6: [0,0,3], [0,1,2], [0,2,1], [1,0,2], [1,1,1], [1,2,0]. - _Alois P. Heinz_, Jun 26 2023
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 15.
%D E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A000707/b000707.txt">Table of n, a(n) for n = 1..1665</a>
%H R. K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>
%H B. H. Margolius, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/inversions.html">Permutations with inversions</a>, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/1888279/number-of-ordered-submultisets-in-a000707">number of ordered multisets in A000707</a>.
%H R. H. Moritz and R. C. Williams, <a href="http://www.jstor.org/stable/2690326">A coin-tossing problem and some related combinatorics</a>, Math. Mag., 61 (1988), 24-29.
%H E. Netto, <a href="http://books.google.fr/books?id=VtIGAAAAYAAJ&pg=PA1&lpg=PA1&dq=Netto,+Lehrbuch+der+Combinatorik&source=bl&ots=bHKKIq5jjf&sig=Mivz_ekDkDAnSMqyXGcfgnqqWfk&hl=en&sa=X&ei=SOyJU96fKO3QsQTlxYDABQ&redir_esc=y">Lehrbuch der Combinatorik</a>, 2nd ed., Teubner, Leipzig, 1st ed., 1901, p. 96.
%H E. Netto, <a href="https://archive.org/details/lehrbuchdercomb00nettgoog">Lehrbuch der Combinatorik</a>, 2nd ed., Teubner, Leipzig, 1st ed., 1901, p. 96.
%H E. Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.
%H Jeffrey Shallit, <a href="/A000707/a000707.pdf">Letter to N. J. A. Sloane, Oct 08 1980</a>
%F See A008302 for g.f.
%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_{n>=1} (1 - 1/(2^n)) = QPochhammer[1/2, 1/2] = 0.288788095... (see A048651), corrected and extended by _Vaclav Kotesovec_, Mar 16 2014
%e 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
%e G.f. = x + x^2 + 2*x^3 + 6*x^4 + 20*x^5 + 71*x^6 + 259*x^7 + 961*x^8 + ...
%p b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
%p `if`(n=0, 1, add(b(n-j, i-1), j=0..min(n, i))))
%p end:
%p a:= n-> b(n-1$2):
%p seq(a(n), n=1..27); # _Alois P. Heinz_, Jun 26 2023
%t 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 *)
%t a[ n_] := SeriesCoefficient[ Product[ Sum[ x^i, {i, 0, k}], {k, 0, n}], {x, 0, n}]; (* _Michael Somos_, Aug 15 2016 *)
%o (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 */
%Y One of the diagonals of triangle in A008302.
%Y Cf. A048651, A129481.
%K nonn,nice,easy
%O 1,3
%A _N. J. A. Sloane_
%E More terms from _James A. Sellers_, Dec 16 1999
%E Asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
%E Better definition from _Joerg Arndt_, Jan 10 2011
|
