
In Many Circles. Permutations as Products of Cycles. 95
s
s
s
s
s
T
s
T
T
T
T
T
T
T
2
6
5
4
9
3
7
8
s
1
2
3
4
6
7
8
9
5
s
FIGURE 3.3
Labeling the edges of T .
construct a bijection h : T
n
→ C
n
,whereC
n
is the set of all (n − 1)-tuples
(s
n
,s
n−1
, ···,s
2
) of transpositions satisfying s
n
s
n−1
s
n−2
···s
2
=(12···n).
Let T ∈ T
n
. Then for every vertex i ∈{2, 3, ···,n}, there is exactly one
path from 1 to i in T .If(a, i) is the last edge in this path, then we label the
edge (a, i)bys
T
i
. See Figure 3.3 for an example.
Let s
i
denote the transposition interchanging the two endpoints of s
i
.Set
C
T
= s
n
T
s
n−1
T
···s
2
T
;thenC
T
is a cyclic permutation because of the previ-
ous lemma. As an intermediate step in