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.")