|
|
COMMENTS
|
Consider the following list of list H = [[1,1,1],[1,1],[1]]. Each sublist L in H is considered as the population of a level of H. We call H a hierarchy.
The levels are counted from the left to the right, thus L_1 = [1,1,1] is the first level. In our example, we have n=3 levels and in total m=6 unlabeled elements "1". The number of elements of level L is called its occupation number O(L). In a strict hierarchy H we have O(L) > O(L+1).
Several types of hierarchies can be constructed. For our example we have chosen that O(L+1) = O(L)+1. Such a hierarchy reminds one of a pyramid, we speak of a pyramidal hierarchy. Since we have n levels, we more precisely speak of a n-pyramidal hierarchy.
Now consider the possible decompositions of H. In decomposition D any numbers of levels may be empty. Furthermore, the number of elements E(L) in D may be less than O(L), thus E(L) <= O(L). Note that in D it is permitted that O(L) < O(L+1). Three examples may be helpful: D = [[1,1],[1],[]] is a decomposition of H. Another one is the empty decomposition D = [[],[],[]] and the third example is D=H.
Finally, find the number a(n) of all allowed decompositions of H(n). This number will depend on what is defined as an allowed decomposition. We can formulate rules on occupation numbers on consecutive levels.
Here we request that decompositions are forbidden if O(L) < O(L+1) and level L+1 is not the empty list []. Then we arrive at what we call an anti-hierarchical decomposition. We have written a small Maple program that carries out the decompositions.
In the unlabeled case we encounter the Bell numbers A000110 and we state: A000110(n) is the number of anti-hierarchical decompositions of an n-pyramidal hierarchy of m=n*(n+1)/2=A000217(n) unlabeled elements.
Example: There are 15 anti-hierarchical decompositions of the 3-pyramidal hierarchy H = [[1,1,1],[1,1],[1]]. They are:
[[], [], []];
[[], [], [1]];
[[], [1], []];
[[], [1], [1]];
[[], [1, 1], []];
[[1], [], []];
[[1], [], [1]];
[[1], [1], []];
[[1], [1], [1]];
[[1], [1, 1], []];
[[1, 1], [], []];
[[1, 1], [], [1]];
[[1, 1], [1, 1], []];
[[1, 1, 1], [], []];
[[1, 1, 1], [], [1]].
From this observation we find the following formula for the Bell numbers (in Latex-like notation):
sum_{l_1=0}^{n} sum_{l_2=0}^{n-1} ... sum_{l_x=0}^{n-x} ... sum_{l_n=0}^{1} delta(l_1, l_2, ..., l_x, ..., l_n)
where
delta(l_1, l_2, ..., l_x, ..., l_n) = 0 if l_x > l_(x+1) and l_(x+1) <> 0 and delta(l_1, l_2, ..., l_x, ..., l_n) = 1 else.
If we impose no rule on the occupation numbers, then we get all possible decompositions D of H. For that case we arrive at a(n)=(n+1)!=A000142(n+1).
Example: There are (3+1)!=24 possible decompositions of the 3-pyramidal hierarchy H = [[1,1,1],[1,1],[1]]. The 15 anti-hierarchical decompositions of these 24 decompositions are given above. If we take labeled elements 1,2,3,... then we can build an n-pyramidal hierarchy from them, too.
Example, for n=3 we again get m=6 and H is now
6
4,5
1,2,3
As in the unlabeled case we determine the number a(n) of anti-hierarchical decompositions of H. By aid of our Maple program we get for n=0,1,2,3,... that a(n) = 1, 2, 7, 39, 346, 5065, 126061,... Thus sequence A153744 is in the sense outlined above a labeled analogy of the Bell numbers. Therefore our definition:
A153744(n) is the number of anti-hierarchical decompositions of an n-pyramidal hierarchy of m=n*(n+1)/2=A000217(n) labeled elements.
As an example we provide the 39 anti-hierarchical decompositions for n=3.
Do not be confused by the labels, instead of 1,2,...,6 it could have been a,b,...,f also. Thus for example [4] is not "higher" than [3], we just focus on the number of elements per sublist.
[[], [], []];
[[], [], [6]];
[[], [4], []];
[[], [4], [6]];
[[], [5], []];
[[], [5], [6]];
[[], [4, 5], []];
[[1], [], []];
[[1], [], [6]];
[[1], [4], []];
[[1], [4], [6]];
[[1], [5], []];
[[1], [5], [6]];
[[1], [4, 5], []];
[[2], [], []];
[[2], [], [6]];
[[2], [4], []];
[[2], [4], [6]];
[[2], [5], []];
[[2], [5], [6]];
[[2], [4, 5], []];
[[1, 2], [], []];
[[1, 2], [], [6]];
[[1, 2], [4, 5], []];
[[3], [], []];
[[3], [], [6]];
[[3], [4], []];
[[3], [4], [6]];
[[3], [5], []];
[[3], [5], [6]];
[[3], [4, 5], []];
[[1, 3], [], []];
[[1, 3], [], [6]];
[[1, 3], [4, 5], []];
[[2, 3], [], []];
[[2, 3], [], [6]];
[[2, 3], [4, 5], []];
[[1, 2, 3], [], []];
[[1, 2, 3], [], [6]].
|
