
COMMENTS

For given n (= number of elements) we consider two hierarchies H1 and H2. We ask whether a onestep transition is possible from H1 to H2 (if it is possible, then there is also a onestep transition from H2 to H1). In a onestep 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 onestep 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 onestep transition does not exist; one needs to move two elements here. For given n, consider the set of all possible unlabeled hierarchies.
How many onestep transitions exist among them? (We count H1 > H2 and H2 > H1 as one transition only, not two. The transition H1 > H1 is a zerostep transition and is not counted.) Answer: For unlabeled hierarchies, one has (with NOOST = number of onestep 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 onestep 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 onestep 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.


EXAMPLE

Consider the unlabeled hierarchies for n = 3 elements. Take for example H1 = [1,2] and H2 = [1,1,1]. A onestep 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 onestep transition is possible.
