login
Number of permutations of [1,2,...,n] with n-1 inversions.
(Formerly M1646 N0644)
16

%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&amp;pg=PA1&amp;lpg=PA1&amp;dq=Netto,+Lehrbuch+der+Combinatorik&amp;source=bl&amp;ots=bHKKIq5jjf&amp;sig=Mivz_ekDkDAnSMqyXGcfgnqqWfk&amp;hl=en&amp;sa=X&amp;ei=SOyJU96fKO3QsQTlxYDABQ&amp;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