9
$\begingroup$

I know that every permutation of a finite set can be decomposed into product of disjoint cycles and every cycle can be decomposed into product of transpositions (cycles of length 2). However the decomposition into transpositions is not unique. I'm aware of at least two "algorithms" for decomposing a cycle into a product of transpositions:

$$(a_1, a_2, \ldots, a_n) = (a_1, a_n)(a_1, a_{n - 1}) \cdots (a_1, a_2)$$

$$(a_1, a_2, \ldots, a_n) = (a_1, a_2)(a_2, a_3) \cdots(a_{n - 1}, a_n)$$

Is there a theorem for counting all possible ways of decomposing a cycle into a product of transpositions (given that I only care about decomposition into $n-1$ transpositions)?

$\endgroup$
8
  • $\begingroup$ The number of products of $n-1$ transpositions is $${n\choose2}^{n-1}$$ The number of $n$-cycles is $(n-1)!$. So cycles have on average $${n\choose2}^{n-1}/(n-1)!$$ decompositions into transpositions. $\endgroup$ Feb 5, 2020 at 12:00
  • $\begingroup$ @WoolierThanThou the cycles $(a_1,a_2,\dots,a_n)$ and (e.g.) $(a_2,a_3,\dots ,a_n,a_1)$ are the same, so if you take all permutations of the symbols $a_1,\dots,a_n$ then you have counted each $n$-cycle $n$ times. $\endgroup$
    – rbrignall
    Feb 5, 2020 at 12:26
  • 5
    $\begingroup$ @GerryMyerson: But not all those products generate $n$-cycles. E.g. you're counting the product of $n-1$ identical transpositions. $\endgroup$
    – joriki
    Feb 5, 2020 at 12:56
  • 4
    $\begingroup$ I wrote some Java code to compute these counts. They seem to be OEIS sequence A000272, which is $n^{n-2}$, the number of trees on $n$ labeled nodes. Interesting. There's a note in the OEIS entry that this is the number of ways of expressing an $n$-cycle as a product of $n-1$ transpositions. It includes an email address but no proof. $\endgroup$
    – joriki
    Feb 5, 2020 at 13:09
  • $\begingroup$ The answer to the general question is actually infinity, since $e$ can be written in infinitely many ways as a product of transpositions (for example your favourite transposition repeated an even number of times, or the above decopositions of your favourier cycle repeated alternately n-1 times). Once you add the restriction in the bracket the question becomes much more interesting. $\endgroup$
    – N. S.
    Feb 10, 2020 at 21:28

1 Answer 1

5
$\begingroup$

If you think of a transposition $(ij)$ as giving an edge for a graph on the vertex set $[n]=\{1,\ldots,n\}$, then you easily see that a product of $n-1$ transpositions forms an $n$-cycle exactly when the underlying graph is a spanning tree on $[n]$. By Cayley's theorem there are $n^{n-2}$ of those. The number of "products" of transpositions that give a big cycle is thus $n^{n-2}\times (n-1)!$ because one also needs to choose the order of the transpositions. So the answer (count per fixed cycle) is $$ \frac{n^{n-2}\times (n-1)!}{(n-1)!}=n^{n-2} $$ as figured out by joriki in the comments. Note that I also used the obvious fact this number of factorizations is the same for all $n$-cycles because the latter are the same up to conjugation.

Note that there is famous article by Dénes which proves the count bijectively: "The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs", Publ. Math. Institute Hung. 4 (1959), 63–70.


In fact, I misquoted Dénes. The truly bijective argument is due to Moskowski in "A Solution to a Problem of Dénes: a Bijection Between Trees and Factorizations of Cyclic Permutations" in EJC 1989.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .