Endofunctions 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

 Endofunctions of given cycle type