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 Mathematics Stack Exchange (see link). - J. M. Bergot, Aug 12 2016
The number of ordered submultisets is found in A129481. - J. M. Bergot, Aug 12 2016
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
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..1665
B. H. Margolius, Permutations with inversions, J. Integ. Seqs. Vol. 4 (2001), #01.2.4.
Mathematics Stack Exchange, number of ordered multisets in A000707.
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.
Jeffrey 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_{n>=1} (1 - 1/(2^n)) = 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 + ...
MAPLE
b:= proc(n, i) option remember; `if`(n>i*(i+1)/2, 0,
`if`(n=0, 1, add(b(n-j, i-1), j=0..min(n, i))))
end:
a:= n-> b(n-1$2):
seq(a(n), n=1..27); # Alois P. Heinz, Jun 26 2023
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
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