Discussion of A109186
Thomas Wieder (thomas.wieder(AT)t-online.de), Mar 29 2008


A109186 gives the number of hierarchical orderings among the subsets of the set     
 partitions of the n-set {1,2,3,...,n}. In order to explain this structure we  
first consider the ordered compositions of compositions (ococs)  of the n-set 
{1,2,3,...,n}, that is sequence A083355(n).  Let the colon ":" be a position 
separator.  We think of hierarchies  where ":" separates two consecutive ranks.    
 The semicolon ";" separates two ococs. For n=2 we have A083355(3)=4.  These 4 
ococs are:

{1:2}; {2:1}; {1,2}; {{1},{2}}.	

An equivalent representation is:

1:2; 2:1; 1,2; {1},{2}.

In the second step, we introduce a second separator "|". Two subsets of a set 
partition belong to two different ococs if they are separated by "|".  In this 
way we introduce multiple ococos for a single set partition. For our example 
with n=2 we get the 5 structures

{1}|{2}; {1}:{2}; {2}:{1}; {1,2}; {{1},{2}}.

Or equivalently:

1|2; 1:2; 2:1; 1,2; {1},{2}.


Thus the hierarchical ordering A109186(n) follows from the application of the 
two separators ":" and "|" on the compositions of n.  A109186 is therefore the 
composition analogon to sequence A075729.  Whereas for A109186 the elements are 
subsets ("groups"), for A075729 the elements may be thought as labeled atoms 
("individuals").  The unlabeled analoga for this point of view are A104525 and 
A034691.


A109186(n) is the log transform of A083355(n). 

A109186(n) is the STIRLINGi transform of A075729(n). If b(n) denotes A109186(n)
 and a(n) denotes A075729(n), then (in Maple notation) 

b(n) = add(stirling2(n,k)*a(k), k=0..n).

For definitions of transforms on integer sequences see:
M. Bernstein & N. J. A. Sloane, Some canonical sequences of integers, 
Linear Algebra and its Applications, 226-228 (1995), 57-72.

Generating function = exp(-(-1+exp(exp(z)-1))/(-2+exp(exp(z)-1)))-1. 
A109186(n) is the log transform of A083355(n).
A109186(n) is the STIRLINGi transform of A075729(n).

We can use combstruct to actually construct the structures A104525(n).
The combstruct command is

with(combstruct);
Test := [V,{V=Set(U),U=Sequence(S,card>=1),S=Set(T,card>=1),T=Set(Z,card>=1)},
labelled]; 
seq(count(Test,size=j),j=1..20);

For n=2 the comstruct command "allstructs(Test,size=2);" returns 

Set(Sequence(Set(Set(Z[1]))),Sequence(Set(Set(Z[2])))),	
Set(Sequence(Set(Set(Z[1])),Set(Set(Z[2])))),		
Set(Sequence(Set(Set(Z[2])),Set(Set(Z[1])))),		
Set(Sequence(Set(Set(Z[2],Z[1])))), 			
Set(Sequence(Set(Set(Z[2]),Set(Z[1])))).

We also give the structures for n=3:

{1,2,3};
{{1,3},{2}};
{1}:{2}:{3};
{1}:{2,3};
{1,2}:{3};
{1}|{2}:{3};
{2,3}|{1};
{{1},{2}},{3};
{{2},{3}}:{1};
{3}:{{1},{2}};	
{{2,3},{1}};
{2}:{1}:{3};
{2}:{1,3};
{1,3}:{2};
{1}|{3}:{2};
{1,2}|{3};
{{2},{3}},{1};
{{1},{3}}:{2};
{2}:{{1},{3}};
{1}|{2}|{3};				
{{1,2},{3}};
{1}:{3}:{2};
{3}:{1,2};
{2,3}:{1};
{2}|{3}:{1};
{1,3}|{2};
{{1},{3}},{2};
{{1},{2}}:{3};
{1}:{{2},{3}};					
{{1},{2},{3}};
{3}:{2}:{1};
{1}:{3}|{2};										
{2}:{3}:{1};
{3}|{2}:{1};								
{3}:{1}:{2};
{3}|{1}:{2}.