The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005651 Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!*n_2!*...) where (n_1, n_2, ...) runs over all integer partitions of n. (Formerly M2870) 116
 1, 1, 3, 10, 47, 246, 1602, 11481, 95503, 871030, 8879558, 98329551, 1191578522, 15543026747, 218668538441, 3285749117475, 52700813279423, 896697825211142, 16160442591627990, 307183340680888755, 6147451460222703502, 129125045333789172825, 2841626597871149750951 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS This is the total number of hierarchies of n labeled elements arranged on 1 to n levels. A distribution of elements onto levels is "hierarchical" if a level l+1 contains <= elements than level l. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed. See also A140585. Examples: Let the colon ":" separate two consecutive levels l and l+1. Then n=2 --> 3: {1}{2}, {1}:{2}, {2}:{1}, n=3 --> 10: {1}{2}{3}, {1}{2}:{3}, {3}{1}:{2}, {2}{3}:{1}, {1}:{2}:{3}, {3}:{1}:{2}, {2}:{3}:{1}, {1}:{3}:{2}, {2}:{1}:{3}, {3}:{2}:{1}. - Thomas Wieder, May 17 2008 n identical objects are painted by dipping them into a long row of cans of paint of distinct colors. Begining with the first can and not skipping any cans k, 1<=k<=n, objects are dipped (painted) and not more objects are dipped into any subsequent can than were dipped into the previous can. The painted objects are then linearly ordered. - Geoffrey Critzer, Jun 08 2009 a(n) is the number of partitions of n where each part i is marked with a word of length i over an n-ary alphabet whose letters appear in alphabetical order and all n letters occur exactly once in the partition. a(3) = 10: 3abc, 2ab1c, 2ac1b, 2bc1a, 1a1b1c, 1a1c1b, 1b1a1c, 1b1c1a, 1c1a1b, 1c1b1a. - Alois P. Heinz, Aug 30 2015 Also the number of ordered set partitions of {1,...,n} with weakly decreasing block sizes. - Gus Wiseman, Sep 03 2018 The parity of a(n) is that of A000110(A000120(n)), so a(n) is even if and only if A000120(n) == 2 (mod 3). - Álvar Ibeas, Aug 11 2020 REFERENCES Abramowitz and Stegun, Handbook, p. 831, column labeled "M_1". L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126. N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..450 (first 101 terms from T. D. Noe) M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. M. E. Hoffman, Updown categories: Generating functions and universal covers, arXiv preprint arXiv:1207.1705 [math.CO], 2012. A. Knopfmacher, A. M. Odlyzko, B. Pittel, L. B. Richmond, D. Stark, G. Szekeres, and N. C. Wormald, The Asymptotic Number of Set Partitions with Unequal Block Sizes, The Electronic Journal of Combinatorics, 6 (1999), R2. S. Schreiber & N. J. A. Sloane, Correspondence, 1980. FORMULA E.g.f.: 1 / Product (1 - x^k/k!). a(n) = Sum_{k=1..n} (n-1)!/(n-k)!*b(k)*a(n-k), where b(k) = Sum_{d divides k} d*d!^(-k/d). - Vladeta Jovovic, Oct 14 2002 a(n) ~ c * n!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264... . - Vaclav Kotesovec, May 09 2014 a(n) = S(n,1), where S(n,m) = sum(k=m..n/2 , binomial(n,k)*S(n-k,k))+1, S(n,n)=1, S(n,m)=0 for n=1} Sum_{j>=1} x^(j*k)/(k*(j!)^k)). - Ilya Gutkovskiy, Jun 18 2018 EXAMPLE For n=3, say the first three cans in the row contain red, white, and blue paint respectively. The objects can be painted r,r,r or r,r,w or r,w,b and then linearly ordered in 1 + 3 + 6 = 10 ways. - Geoffrey Critzer, Jun 08 2009 From Gus Wiseman, Sep 03 2018: (Start) The a(3) = 10 ordered set partitions with weakly decreasing block sizes:   {{1},{2},{3}}   {{1},{3},{2}}   {{2},{1},{3}}   {{2},{3},{1}}   {{3},{1},{2}}   {{3},{2},{1}}   {{2,3},{1}}   {{1,2},{3}}   {{1,3},{2}}   {{1,2,3}} (End) MAPLE A005651b := proc(k) add( d/(d!)^(k/d), d=numtheory[divisors](k)) ; end proc: A005651 := proc(n) option remember; local k ; if n <= 1 then 1; else (n-1)!*add(A005651b(k)*procname(n-k)/(n-k)!, k=1..n) ; end if; end proc: seq(A005651(k), k=0..10) ; # R. J. Mathar, Jan 03 2011 # second Maple program: b:= proc(n, i) option remember; `if`(n=0 or i=1, n!,       b(n, i-1) +binomial(n, i)*b(n-i, min(n-i, i)))     end: a:= n-> b(n\$2): seq(a(n), n=0..25);  # Alois P. Heinz, Aug 29 2015, Dec 12 2016 MATHEMATICA Table[Total[n!/Map[Function[n, Apply[Times, n! ]], IntegerPartitions[n]]], {n, 0, 20}] (* Geoffrey Critzer, Jun 08 2009 *) Table[Total[Apply[Multinomial, IntegerPartitions[n], {1}]], {n, 0, 20}] (* Jean-François Alcover and Olivier Gérard, Sep 11 2014 *) b[n_, i_, t_] := b[n, i, t] = If[t==1, 1/n!, Sum[b[n-j, j, t-1]/j!, {j, i, n/t}]]; a[n_] := If[n==0, 1, n!*b[n, 0, n]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 20 2015, after Alois P. Heinz *) PROG (Maxima) a(m, n):=if n=m then 1 else sum(binomial(n, k)*a(k, n-k), k, m, (n/2))+1; makelist(a(1, n), n, 0, 17); /* Vladimir Kruchinin, Sep 06 2014 */ (PARI) a(n)=my(N=n!, s); forpart(x=n, s+=N/prod(i=1, #x, x[i]!)); s \\ Charles R Greathouse IV, May 01 2015 (PARI) { my(n=25); Vec(serlaplace(prod(k=1, n, 1/(1-x^k/k!) + O(x*x^n)))) } \\ Andrew Howroyd, Dec 20 2017 CROSSREFS Main diagonal of: A226873, A261719, A309973. Row sums of: A226874, A262071, A327803. Column k=1 of A309951. Column k=0 of A327801. Cf. A000041, A000110, A000258, A000670, A007837, A008277, A008480, A036038, A140585, A178682, A212855, A247551, A300335, A318762. Sequence in context: A226878 A226879 A226880 * A249479 A236410 A339836 Adjacent sequences:  A005648 A005649 A005650 * A005652 A005653 A005654 KEYWORD nonn,easy,nice AUTHOR EXTENSIONS More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 13 10:21 EDT 2021. Contains 344985 sequences. (Running on oeis4.)