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
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<m. - Vladimir Kruchinin, Sep 06 2014
E.g.f.: exp(Sum_{k>=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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
STATUS
approved