login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A140585 Total number of all hierarchical orderings for all set partitions of n. 9
1, 4, 20, 129, 1012, 9341, 99213, 1191392, 15958404, 235939211, 3817327362, 67103292438, 1273789853650, 25973844914959, 566329335460917, 13150556885604115, 324045146807055210, 8446201774570017379, 232198473069120178475, 6715304449424099384968 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 1..420 (first 160 terms from Alois P. Heinz)

Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [Thomas Wieder, Nov 14 2009]

FORMULA

Stirling transform of A005651 = Sum of multinomial coefficients: a(n) = Sum_{i=1..n} S2(n,k) A005651(k).

E.g.f.: 1/Product_{k>=1} (1 - (exp(x)-1)^k/k!). - Thomas Wieder, Sep 04 2008

a(n) ~ c * n! / (log(2))^n, where c = 1/(2*log(2)) * Product_{k>=2} 1/(1-1/k!) = A247551 / (2*log(2)) = 1.82463230250447246267598544320244231645906135137... . - Vaclav Kotesovec, Sep 04 2014, updated Jan 21 2017

EXAMPLE

We are considering all set partitions of the n-set {1,2,3,...,n}.

For each such set partition we examine all possible hierarchical arrangements of the subsets. A hierarchy is a distribution of elements (sets in the present case) onto levels.

A distribution onto levels is "hierarchical" if a level l+1 contains less or equal elements than the level l. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed.

Let the colon ":" separate two consecutive levels l and l+1.

n=2 --> 1+3=4

{1,2} {1}{2}

{1}:{2}

{2}:{1}

n=3 --> 1+9+10=20

1*1 3*3=9 1*10

{1,2,3} {1,2}{3} {1}{2}{3}

{1,3}{2}

{2,3}{1} {1}{2}:{3}

{3}{1}:{2}

{1,2}:{3} {2}{3}:{1}

{1,3}:{2}

{2,3}:{1} {1}:{2}:{3}

{3}:{1}:{2}

{3}:{1,2} {2}:{3}:{1}

{2}:{1,3} {1}:{3}:{2}

{1}:{2,3} {2}:{1}:{3}

{3}:{2}:{1}

n=4 --> 1+12+9+60+47=129

1*1 4*3=12 3*3=9 6*10=60 1*47

{1,2,3,4} {1,2,3}{4} {1,2}{3,4} {1,2}{3}{4} {1}{2}{3}{4}

{1,2,4}{3} {1,3}{2,4} {1,2}{3}:{4}

{1,3,4}{2} {1,4}{2,3} {1,2}{4}:{3} {1}{2}:{3}:{4}

{2,3,4}{1} {1}{2}:{3,4} {1}{3}:{2}:{4}

{1,2}:{3,4} {1,2}:{3}:{4} {1}{4}:{2}:{3}

{1,2,3}:{4} {1,3}:{2,4} {1,2}:{4}:{3} {1}{2}:{4}:{3}

{1,2,4}:{3} {1,4}:{2,3} {1}:{2}:{3,4} {1}{3}:{4}:{2}

{1,3,4}:{2} {3,4}:{1,2} {2}:{1}:{3,4} {1}{4}:{3}:{2}

{2,3,4}:{1} {2,4}:{1,3} {1}:{3,4}:{2}

{2,3}:{1,4} {2}:{3,4}:{1} {2}{3}:{1}:{4}

{4}:{1,2,3} {2}{4}:{1}:{3}

{3}:{1,2,4} likewise for: {2}{3}:{4}:{1}

{2}:{1,3,4} {3,4}{1}{2} {2}{4}:{3}:{1}

{1}:{2,3,4} {2,4}{1}{3}

{2,3}{1}{4} {3}{4}:{1}:{2}

{1,4}{2}{3} {3}{4}:{2}:{1}

{1,3}{2}{4}

{1}{2}:{3}{4}

{1}{3}:{2}{4}

{1}{4}:{2}{3}

{2}{3}:{1}{4}

{2}{4}:{1}{3}

{3}{4}:{1}{2}

{2}{3}{4}:{1}

{1}{3}{4}:{2}

{1}{2}{4}:{3}

{1}{2}{3}:{4}

{1}:{2}:{3}:{4}

+23 permutations

MAPLE

A140585 := proc(n::integer) local k, Result; Result:=0: for k from 1 to n do Result:=Result+stirling2(n, k)*A005651(k); end do; lprint(Result); end proc;

E.g.f.: series(1/mul(1-(exp(x)-1)^k/k!, k=1..10), x=0, 10). # Thomas Wieder, Sep 04 2008

# second Maple program:

with(numtheory): b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end: c:= proc(n) option remember; `if`(n=0, 1, add((n-1)!/ (n-k)!* b(k)* c(n-k), k=1..n)) end: a:= n-> add(Stirling2(n, k) *c(k), k=1..n): seq(a(n), n=1..30); # Alois P. Heinz, Oct 10 2008

MATHEMATICA

Table[n!*SeriesCoefficient[1/Product[(1-(E^x-1)^k/k!), {k, 1, n}], {x, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Sep 03 2014 *)

CROSSREFS

Cf. A005651, A075729, A034691, A083355, A109186, A000670.

Sequence in context: A126674 A196557 A082032 * A132436 A307006 A208735

Adjacent sequences:  A140582 A140583 A140584 * A140586 A140587 A140588

KEYWORD

nonn

AUTHOR

Thomas Wieder, May 17 2008

EXTENSIONS

More terms from Alois P. Heinz, Oct 10 2008

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 20:36 EST 2020. Contains 330987 sequences. (Running on oeis4.)