A089378 Number of one-step transitions between all unlabeled hierarchies of n elements.

0, 6, 24, 104, 382, 1414, 4870

Offset: 1

Author

Thomas Wieder, Dec 27 2003

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A034691, A049611, A075729, A093694.

Programs

Maple

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