login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089378 Number of one-step transitions between all unlabeled hierarchies of n elements. 3
0, 6, 24, 104, 382, 1414, 4870 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

For given n (= number of elements) we consider two hierarchies H1 and H2. We ask whether a one-step transition is possible from H1 to H2 (if it is possible, then there is also a one-step transition from H2 to H1). In a one-step transition just one single element is moved from its position in H1 to its position in H2.

For example, consider n=4 and H1 = [[2], [2]], H2 = [[2], [1, 1]]. H1 consists of two subhierarchies S1H1 = [2] and S2H1 = [2] with two elements on level 1 in both cases. In H2, we have S1H2 = [2] and S2H2 = [1,1] which means one element on level 1 and one element on level 2 in S2H2. A one-step transition is possible, just move one element in S2H1 (or S1H1) from level 1 to level 2.

As a counterexample, for H1 = [[2], [2]] and H2 = [[1], [1, 1, 1]], a one-step transition does not exist; one needs to move two elements here. For given n, consider the set of all possible unlabeled hierarchies.

How many one-step transitions exist among them? (We count H1 -> H2 and H2 -> H1 as one transition only, not two. The transition H1 -> H1 is a zero-step transition and is not counted.) Answer: For unlabeled hierarchies, one has (with NOOST = number of one-step transitions) n = 1, NOOST = 0; n = 2, NOOST = 3; n = 3, NOOST = 12; n = 4, NOOST = 51; n = 5, NOOST = 175; n = 6, NOOST = 570; n = 7, NOOST = 1914.

We may ask for the number of one-step transitions (NOOST) between all unlabeled hierarchies of n elements with the restriction that no subhierarchies are allowed. As an example, consider n = 4 and the hierarchy H1 = [[2,2]] with two elements on level 1 and two on level 2. Starting from H1 the hierarchies [[1, 3]], [[2, 1, 1]], [[1, 2, 1]] can be reached by moving one element only, but [[1, 1, 2]] cannot be reached in a one-step transitition. The solution is n = 1, NOOST = 0; n = 2, NOOST = 1; n = 3, NOOST = 4; n = 4, NOOST = 13; n = 5, NOOST = 38; n = 6, NOOST = 104; n = 7, NOOST = 272; n = 8, NOOST = 688; n = 9, NOOST = 1696. This is sequence A049611.

LINKS

Table of n, a(n) for n=1..7.

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

EXAMPLE

Consider the unlabeled hierarchies for n = 3 elements. Take for example H1 = [1,2] and H2 = [1,1,1]. A one-step transition is possible between H1 and H2 by moving one element of the second level (occupied by two elements) of H1 on the third level, which gives H2.

As a counterexample, consider H1 and H3 = [[1], [1], [1]]. H3 consists of three subhierarchies. In order to get from H1 to H3 one needs to move two elements; no one-step transition is possible.

MAPLE

A (rather long) Maple program is available from the author.

CROSSREFS

Cf. A034691, A049611, A075729, A093694.

Sequence in context: A126393 A265697 A120583 * A074414 A165793 A122740

Adjacent sequences:  A089375 A089376 A089377 * A089379 A089380 A089381

KEYWORD

nonn

AUTHOR

Thomas Wieder, Dec 27 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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 22:06 EST 2019. Contains 329963 sequences. (Running on oeis4.)