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

 

Logo


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 April 11 12:00 EDT 2021. Contains 342886 sequences. (Running on oeis4.)