# [GAP Forum] Re: reply to GAP forum question

Thomas Breuer thomas.breuer at math.rwth-aachen.de
Fri Sep 3 17:42:31 BST 2004

```Dear GAP Forum,

The GAP code below provides this.

All the best,
Thomas

#############################################################################
##
#M  Enumerator( <M> ) . . . . . . . . . . . . . . enumerator for a free magma
##
BindGlobal( "CATALAN", [ 1 ] );

BindGlobal( "Catalan", function( n )
if not IsBound( CATALAN[n+1] ) then
CATALAN[n+1]:= Binomial( 2*n, n ) / ( n+1 );
fi;
return CATALAN[n+1];
end );

BindGlobal( "ElementNumber_FreeMagma", function( enum, nr )
local WordFromInfo, n, l, summand, NB, q, p;

# Create the external representation (recursively).
WordFromInfo:= function( N, l, p, q )
local k, NB, summand, Nk, p1, p2, q1, q2;;

if l = 1 then
return p;
fi;

k:= 0;
while 0 < q do
k:= k+1;
NB:= Catalan( l-k-1 );
summand:= Catalan( k-1 ) * NB;
q:= q - summand;
od;
q:= q + summand;

Nk:= N^k;
p1:= p mod Nk;
if p1 = 0 then
p1:= Nk;
fi;
p2:= ( p - p1 ) / Nk + 1;

q2:= q mod NB;
if q2 = 0 then
q2:= NB;
fi;
q1:= ( q - q2 ) / NB + 1;

return [ WordFromInfo( N, k,   p1, q1 ),
WordFromInfo( N, l-k, p2, q2 ) ];
end;

n:= enum!.nrgenerators;

l:= 0;
while 0 < nr do
NB:= Catalan( l );
l:= l+1;
summand:= n^l * NB;
nr:= nr - summand;
od;
nr:= nr + summand;

q:= nr mod NB;
if q = 0 then
q:= NB;
fi;

p:= ( nr - q ) / NB + 1;

return ObjByExtRep( enum!.family, WordFromInfo( n, l, p, q ) );
end );

BindGlobal( "NumberElement_FreeMagma", function( enum, elm )
local WordInfo, n, info, pos, i;

if not IsCollsElms( FamilyObj( enum ), FamilyObj( elm ) ) then
return fail;
fi;

# Analyze the structure (recursively).
WordInfo:= function( ngens, obj )
local info1, info2, N;

if IsInt( obj ) then
return [ ngens, 1, obj, 1 ];
else
info1:= WordInfo( ngens, obj[1] );
info2:= WordInfo( ngens, obj[2] );
N:= info1[2] + info2[2];
return [ ngens, N,
info1[3]+ ngens^info1[2] * ( info2[3]-1 ),
Sum( List( [ 1 .. info1[2]-1 ],
i -> Catalan( i-1 ) * Catalan( N-i-1 ) ), 0 )
+ ( info1[4] - 1 ) * Catalan( info2[2]-1 ) + info2[4] ];
fi;
end;

# Calculate the length, the number of the corresponding assoc. word,
# and the number of the bracketing.
n:= enum!.nrgenerators;
info:= WordInfo( n, ExtRepOfObj( elm ) );

# Compute the position.
pos:= 0;
for i in [ 1 .. info[2]-1 ] do
pos:= pos + n^i * Catalan( i-1 );
od;
return pos + ( info[3] - 1 ) * Catalan( info[2]-1 ) + info[4];
end );

InstallMethod( Enumerator,
"for a free magma",
[ IsWordCollection and IsWholeFamily and IsMagma ],
function( M )

# A free associative structure needs another method.
if IsAssocWordCollection( M ) then
TryNextMethod();
fi;

return EnumeratorByFunctions( M, rec(
ElementNumber := ElementNumber_FreeMagma,
NumberElement := NumberElement_FreeMagma,

family       := ElementsFamily( FamilyObj( M ) ),
nrgenerators := Length( ElementsFamily(
FamilyObj( M ) )!.names ) ) );
end );

```