cp's OEIS Frontend

A000707 Number of permutations of [1,2,...,n] with n-1 inversions.

%I A000707 M1646 N0644 #94 Jul 02 2025 16:01:53
%S A000707 1,1,2,6,20,71,259,961,3606,13640,51909,198497,762007,2934764,
%T A000707 11333950,43874857,170193528,661386105,2574320659,10034398370,
%U A000707 39163212165,153027659730,598577118991,2343628878849,9184197395425,36020235035016,141376666307608
%N A000707 Number of permutations of [1,2,...,n] with n-1 inversions.
%C A000707 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 A000707 For a more general result (taking multisubset of any size) see A008302. - _Jacob Post_, Jan 03 2011
%C A000707 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 A000707 The number of ordered submultisets is found in A129481. - _J. M. Bergot_, Aug 12 2016
%C A000707 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 A000707 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 241.
%D A000707 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.14., p.356
%D A000707 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 15.
%D A000707 E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 96.
%D A000707 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000707 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000707 Alois P. Heinz, <a href="/A000707/b000707.txt">Table of n, a(n) for n = 1..1665</a>
%H A000707 R. K. Guy, <a href="/A000707/a000707_2.pdf">Letter to N. J. A. Sloane with attachment, Mar 1988</a>
%H A000707 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 A000707 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 A000707 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 A000707 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 A000707 E. Netto, <a href="https://archive.org/details/lehrbuchdercomb00nettgoog">Lehrbuch der Combinatorik</a>, 2nd ed., Teubner, Leipzig, 1st ed., 1901, p. 96.
%H A000707 E. Netto, <a href="/A000707/a000707_1.pdf">Lehrbuch der Combinatorik</a>, Chapter 4, annotated scanned copy of pages 92-99 only.
%H A000707 Jeffrey Shallit, <a href="/A000707/a000707.pdf">Letter to N. J. A. Sloane, Oct 08 1980</a>
%F A000707 See A008302 for g.f.
%F A000707 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 A000707 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 A000707 G.f. = x + x^2 + 2*x^3 + 6*x^4 + 20*x^5 + 71*x^6 + 259*x^7 + 961*x^8 + ...
%p A000707 b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
%p A000707       `if`(n=0, 1, add(b(n-j, i-1), j=0..min(n, i))))
%p A000707     end:
%p A000707 a:= n-> b(n-1$2):
%p A000707 seq(a(n), n=1..27);  # _Alois P. Heinz_, Jun 26 2023
%t A000707 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 A000707 a[ n_] := SeriesCoefficient[ Product[ Sum[ x^i, {i, 0, k}], {k, 0, n}], {x, 0, n}]; (* _Michael Somos_, Aug 15 2016 *)
%o A000707 (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 A000707 One of the diagonals of triangle in A008302.
%Y A000707 Cf. A048651, A129481.
%K A000707 nonn,nice,easy
%O A000707 1,3
%A A000707 _N. J. A. Sloane_
%E A000707 More terms from _James Sellers_, Dec 16 1999
%E A000707 Asymptotic formula from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), May 31 2001
%E A000707 Better definition from _Joerg Arndt_, Jan 10 2011