Comments on A034899 from Thomas Wieder (wieder.thomas(AT)t-online.de), Mar 06 2005

This is also the number of 2-classes hierarchies.

The number of hierarchical orderings for n unlabeled elements (see A034691) when in addition the elements can be distributed over k=2 classes.

Consider a hierarchy of n unlabeled elements where hierarchy is meant in the sense of A034691. Thus the n elements not only can be distributed over up to n ranks but also split into at most n different groups (boxes, societies"). E.g. for n=4 there are 18 different hierarchies possible. Now we introduce classes into the consideration. Here we treate the case of k=2 classes A and B. The classes may represent certain attributes which can be assigned to the elements (e.g. my elements, your elements). Then we arrive at a k-dimensional hierarchy. How many 2-dimensional hierarchies exist?

Let OP(i,2,n) denote the i-th ordered partition of n into 2 parts. E.g. OP(1,2,4)=1+3, OP(2,2,4)=3+1, OP(3,2,4)=2+2. Furthermore, let p_j be the j-th part of OP(i,2,n), e.g. there are the parts p_1=1 and p_2=3 in OP(1,2,4). The sum Sum_(OP(i,2,n)) is meant to run over all ordered partitions of n into 2 parts. The product Prod_(j=1)^(2) is meant to run over the parts p_1 to p_2 of the i-th ordered partition. UH(n) (A034691) is the number of hierarchies for unlabeled elements in the case of one class only.

Then the number of hierarchies with elements in both classes A and B is Sum_(OP(i,2,n)) Prod_(j=1)^(2) UH(p_j).

E.g. for n=4, OP(1,2,4) contributes UH(1)*UH(3)=1*7, OP(2,2,4) contributes UH(3)*UH(1)=7*1, OP(3,2,4) contributes UH(2)*UH(2)=3*3, thus there are 7+7+9=23 hierarchies with elements in both classes.

For n unlabeled elements the total number a(n) of hierarchies with elements either solely in class A, solely in class B, or in both classes A and B is a(n) = 2*UH(n) + Sum_(OP(i,2,n)) Prod_(j=1)^(2) UH(p_j) or equivalently a(n)= 2*A034691(n) + Sum_(OP(i,2,n)) Prod_(j=1)^(2) A034691(p_j).

E.g. for n=4 one finally has 2*18+23=59 possible 2-class hierarchies.

Let "a" and "b" be elements situated in the classes A and B. Let : be a
separator among levels (ranks). Let | be a separator among groups. E.g.
a:a|a is a hierarchy composed of two groups. The first group contains
three elements with two elements "a" on level 1 and one "a" on level 2.

The second group has just one element "a" (placed on rank 1). The two
classes will be separated by a comma. In order to desinate the membership
of an element to either A or B we write a or b for that element although it is unlabeled.

For n=4 there are 23 hierarchies with elements in both classes:
aaa,b; aa:a,b; a:aa,b; aa|a,b; a:a|a,b; a|a|a,b; a:a:a,b
a,bbb; a,bb:b; a,b:bb; a,bb|b; a,b:b|b; a,b|b|b; a,b:b:b
aa,bb; aa,b:b; aa,b|b;
a:a,bb; a:a,b:b; a:a,b|b;
a|a,bb; a|a,b:b, a|a,b|b;

A two-dimensional representation is easier to understand. It will be a
field of n*2 boxes. Along the dimension connected to the factor n one
has the groups (boxes) into which one can split the elements. Along the
dimension of the factor 2 one has the both classes A and B. Ranking
among elements is indicated by stapling the elements. Two examples for n=4:

Example 1:
--------------
I.....I...b..I
I..a..I...b..I
--------------
I..a...I......I = a|a,b:b
--------------
I......I......I
--------------
I......I......I
--------------

Example 2:
--------------
I......I......I
I..aa..I...b..I
--------------
I..a...I......I = aa|a,b
--------------
I......I......I
--------------
I......I......I
--------------

Cf. A034691, A075729.