|
EXAMPLE
|
We are considering all set partitions of the n-set {1,2,3,...,n}.
For each such set partition we examine all possible hierarchical arrangements of the subsets. A hierarchy is a distribution of elements (sets in the present case) onto levels.
A distribution onto levels is "hierarchical" if a level L+1 contains at most as many elements as level L. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed.
Let the colon ":" separate two consecutive levels L and L+1.
n=2 --> 1+3=4
{1,2} {1}{2}
{1}:{2}
{2}:{1}
-----------------------
n=3 --> 1+9+10=20
1*1 3*3=9 1*10
{1,2,3} {1,2}{3} {1}{2}{3}
{1,3}{2}
{2,3}{1} {1}{2}:{3}
{3}{1}:{2}
{1,2}:{3} {2}{3}:{1}
{1,3}:{2}
{2,3}:{1} {1}:{2}:{3}
{3}:{1}:{2}
{3}:{1,2} {2}:{3}:{1}
{2}:{1,3} {1}:{3}:{2}
{1}:{2,3} {2}:{1}:{3}
{3}:{2}:{1}
-----------------------
n=4 --> 1+12+9+60+47=129
1*1 4*3=12 3*3=9 6*10=60 1*47
{1,2,3,4} {1,2,3}{4} {1,2}{3,4} {1,2}{3}{4} {1}{2}{3}{4}
{1,2,4}{3} {1,3}{2,4} {1,2}{3}:{4}
{1,3,4}{2} {1,4}{2,3} {1,2}{4}:{3} {1}{2}:{3}:{4}
{2,3,4}{1} {1}{2}:{3,4} {1}{3}:{2}:{4}
{1,2}:{3,4} {1,2}:{3}:{4} {1}{4}:{2}:{3}
{1,2,3}:{4} {1,3}:{2,4} {1,2}:{4}:{3} {1}{2}:{4}:{3}
{1,2,4}:{3} {1,4}:{2,3} {1}:{2}:{3,4} {1}{3}:{4}:{2}
{1,3,4}:{2} {3,4}:{1,2} {2}:{1}:{3,4} {1}{4}:{3}:{2}
{2,3,4}:{1} {2,4}:{1,3} {1}:{3,4}:{2}
{2,3}:{1,4} {2}:{3,4}:{1} {2}{3}:{1}:{4}
{4}:{1,2,3} {2}{4}:{1}:{3}
{3}:{1,2,4} likewise for: {2}{3}:{4}:{1}
{2}:{1,3,4} {3,4}{1}{2} {2}{4}:{3}:{1}
{1}:{2,3,4} {2,4}{1}{3}
{2,3}{1}{4} {3}{4}:{1}:{2}
{1,4}{2}{3} {3}{4}:{2}:{1}
{1,3}{2}{4}
{1}{2}:{3}{4}
{1}{3}:{2}{4}
{1}{4}:{2}{3}
{2}{3}:{1}{4}
{2}{4}:{1}{3}
{3}{4}:{1}{2}
{2}{3}{4}:{1}
{1}{3}{4}:{2}
{1}{2}{4}:{3}
{1}{2}{3}:{4}
{1}:{2}:{3}:{4}
+23 permutations
|