|
%I M2870 #137 Oct 27 2023 19:48:24
%S 1,1,3,10,47,246,1602,11481,95503,871030,8879558,98329551,1191578522,
%T 15543026747,218668538441,3285749117475,52700813279423,
%U 896697825211142,16160442591627990,307183340680888755,6147451460222703502,129125045333789172825,2841626597871149750951
%N Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!*n_2!*...) where (n_1, n_2, ...) runs over all integer partitions of n.
%C 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
%C 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
%C 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
%C Also the number of ordered set partitions of {1,...,n} with weakly decreasing block sizes. - _Gus Wiseman_, Sep 03 2018
%C 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
%D Abramowitz and Stegun, Handbook, p. 831, column labeled "M_1".
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126.
%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="/A005651/b005651.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
%H M. E. Hoffman, <a href="http://arxiv.org/abs/1207.1705">Updown categories: Generating functions and universal covers</a>, arXiv preprint arXiv:1207.1705 [math.CO], 2012.
%H A. Knopfmacher, A. M. Odlyzko, B. Pittel, L. B. Richmond, D. Stark, G. Szekeres, and N. C. Wormald, <a href="https://doi.org/10.37236/1434">The Asymptotic Number of Set Partitions with Unequal Block Sizes</a>, The Electronic Journal of Combinatorics, 6 (1999), R2.
%H S. Schreiber & N. J. A. Sloane, <a href="/A006368/a006368.pdf">Correspondence, 1980</a>.
%F E.g.f.: 1 / Product (1 - x^k/k!).
%F 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
%F a(n) ~ c * n!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264... . - _Vaclav Kotesovec_, May 09 2014
%F 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<m. - _Vladimir Kruchinin_, Sep 06 2014
%F E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} x^(j*k)/(k*(j!)^k)). - _Ilya Gutkovskiy_, Jun 18 2018
%e 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
%e From _Gus Wiseman_, Sep 03 2018: (Start)
%e The a(3) = 10 ordered set partitions with weakly decreasing block sizes:
%e {{1},{2},{3}}
%e {{1},{3},{2}}
%e {{2},{1},{3}}
%e {{2},{3},{1}}
%e {{3},{1},{2}}
%e {{3},{2},{1}}
%e {{2,3},{1}}
%e {{1,2},{3}}
%e {{1,3},{2}}
%e {{1,2,3}}
%e (End)
%p A005651b := proc(k) add( d/(d!)^(k/d),d=numtheory[divisors](k)) ; end proc:
%p 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:
%p seq(A005651(k), k=0..10) ; # _R. J. Mathar_, Jan 03 2011
%p # second Maple program:
%p b:= proc(n, i) option remember; `if`(n=0 or i=1, n!,
%p b(n, i-1) +binomial(n, i)*b(n-i, min(n-i, i)))
%p end:
%p a:= n-> b(n$2):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Aug 29 2015, Dec 12 2016
%t Table[Total[n!/Map[Function[n, Apply[Times, n! ]], IntegerPartitions[n]]], {n, 0, 20}] (* _Geoffrey Critzer_, Jun 08 2009 *)
%t Table[Total[Apply[Multinomial, IntegerPartitions[n], {1}]], {n, 0, 20}] (* _Jean-François Alcover_ and _Olivier Gérard_, Sep 11 2014 *)
%t 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_ *)
%o (Maxima)
%o a(m,n):=if n=m then 1 else sum(binomial(n,k)*a(k,n-k),k,m,(n/2))+1;
%o makelist(a(1,n),n,0,17); /* _Vladimir Kruchinin_, Sep 06 2014 */
%o (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
%o (PARI) { my(n=25); Vec(serlaplace(prod(k=1, n, 1/(1-x^k/k!) + O(x*x^n)))) } \\ _Andrew Howroyd_, Dec 20 2017
%Y Main diagonal of: A226873, A261719, A309973.
%Y Row sums of: A226874, A262071, A327803.
%Y Column k=1 of A309951.
%Y Column k=0 of A327801.
%Y Cf. A000041, A000110, A000258, A000670, A007837, A008277, A008480, A036038, A140585, A178682, A212855, A247551, A300335, A318762.
%K nonn,easy,nice
%O 0,3
%A _Simon Plouffe_
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
|
