login
This site is supported by donations to The OEIS 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. 8
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

REFERENCES

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

LINKS

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

FORMULA

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

E.g.f.: 1/prod_{k=1}^{inf} (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 A208735 A038173

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 15 19:23 EST 2019. Contains 319171 sequences. (Running on oeis4.)