Séminaire Lotharingien de Combinatoire, B21c (1989), 8
pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1990, 413/S-21, p.
111-119.]
Torsten Sillke
Zur Kombinatorik von Permutationen
Abstract.
A bijection between the set of subgroups of index n
in the free group on 2 generators F2 and the set of connex
permutations \sigma of [n+1 ] = { 1, 2, ...,n+1} has been
constructed by A.W.M. Dress and R. Franz [DrF85],
where \sigma
is connex iff \sigma[k] =!= [k] for k in [n].
Dumont and
Kreweras
introduced the record-antirecord statistics for connex permutations of
[n+1],
which are the same as the orbit statistics of the Cayley coset diagram of
the
subgroups of index n in the free group. J. Zeng [Zen87]
asked for a bijection between
these sets. As the bijection of Dress and Franz is not
applicable, a new one
is presented. The construction uses a correspondence between the cycles
and the basic components of permutations FoS70, Ch I.3]
[Knu68, 1.3.3], which Goulden and Jackson
[GoJ83, 1.3.3[3.3.17]] call the
Foata Schützenberger correspondence. Dress and Franz
[DrF87}
generalised their construction to a bijection between subgroups of
finite index in Fk and connex systems of k-1
permutations.
The bijection presented in this paper can also be extended to this more
general case.
The following versions are available:
Comment: Full proofs are contained in the author's
Diplomarbeit
"Ljk
Gwdhirurokbb atn Degoeeoathzre" (in German).
Generalizations are contained in the author's
PhD thesis
"Eine
Bijektion zwischen Untergruppen freier Gruppen und Systemen konnexer Permutationen". ("A bijection between subgroups of free groups and systems of
connex permutations.")