Combinatorics of the fullerenesApplicationsEnumeration of isometry classes of linear codesEndofunctions of given cycle type

Endofunctions of given cycle type

In [9] it is described how to enumerate endofunctions on a finite set X (these are functions having the same set X as domain and range) of given cycle type. (I.e. iteration of an endofunction gives rise to cycles of this function.) Let an INTEGER n, the number of elements in the domain, a set L of cycle lengths and for each l ÎL the multiplicity m(l ) of the occurrence of a cycle of length l be given. Then the number of endofunctions having exactly m(l ) cycles of length l for each l ÎL (some further cycles of length l not ÎL may occur) can be computed by   
INT endof_week_cycletype(n,L,m,erg)   OP n,L,m,erg;
The set L is coded as a VECTOR L such that S_V_I(L,i) for i=0,...,S_V_LI(L)-1 are all the prescribed cycle lengths. The multiplicity of the cycle length S_V_I(L,i) must be described in S_V_I(m,i). (m is a VECTOR object of the same length as L.) The multiplicities must be chosen from the set {0,1,2,...} . The number of elements in the domain and range is given by the INTEGER object n, and erg is the number of all endofunctions having these prescribed cycle properties.

Renaming the elements of X leads to a group action on the set of all endofunctions on X. The number of orbits of endofunctions of prescribed cycle properties can be computed by   

INT endof_orbits_week_cycletype(n,L,m,erg)   OP n,L,m,erg;

In the case when the cycle type of an endofunction is prescribed (i.e. the set L is given by {1,2,...,|X|} ) then the two routines above can be replaced by   

INT endof_of_cycletype(n,m,erg)          OP n,m,erg;
INT endof_orbits_of_cycletype(n,m,erg)   OP n,m,erg;
where n is the cardinality of X, m is a VECTOR object such that for i=0,...,n-1 the INTEGER object S_V_I(m,i) gives the multiplicity of the length i+1.

As a special case of the formulae above we can compute the number of all rooted trees using the routine   

INT rooted_trees_from_zykelind(a,b)    OP a,b;
where b is the number of rooted trees on a nodes. (The root is considered to be one of the nodes.)

There is a recursive routine for enumerating rooted trees as well:   

INT rooted_trees_rec(a,b)    OP a,b;
where b is the number of rooted trees on a nodes.

For enumerating functional digraphs (these are endofunctions having no fixed points) you can use   

INT functional_digraphs(a,b)   OP a,b;
where b is the number of functional digraphs on a vertices.

When preparing [9] we found a recursive formula for determining the number of all endofunctions on X having no cycles of length l for all l in a given set L of cycle lengths. This formula is used in   

INT schoepf_rec(n,L,erg)     OP n,L,erg;
where n is the cardinality of X, L is a VECTOR object the entries of which are the cycle lengths that may not occur and erg is the number of all the endofunctions with these properties.
harald.fripertinger@kfunigraz.ac.at,
last changed: November 19, 2001

Combinatorics of the fullerenesApplicationsEnumeration of isometry classes of linear codesEndofunctions of given cycle type