| | | **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** |