Labelled trees and factorizations of a cycle into transpositions (Q2366027)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Labelled trees and factorizations of a cycle into transpositions |
scientific article |
Statements
Labelled trees and factorizations of a cycle into transpositions (English)
0 references
29 June 1993
0 references
In [Publ. Math. Inst. Hung. Acad. Sci. 4, 63-70 (1959; Zbl 0092.011)] the reviewer proved that the set of \((n-1)\)-tuples of transpositions in \(S_ n\) whose ordered product is a complete cycle, is \(n^{n-2}\). \textit{A. Cayley} [Quart. J. Math. Oxford 23, 376-378 (1889)] proved that the number of labelled trees with \(n\) vertices is \(n^{n-2}\). The reviewer's proof based on a one to one correspondance between \((n-1)!| A_ n|\) and \((n-1)!| B_ n|\) where \(| A_ n|\) denote the cardinality of the set of labelled trees on \(n\) vertices and \(| B_ n|\) denotes the cardinality of the set of \((n-1)\)-tuples of transpositions in \(S_ n\) whose ordered product is a complete cycle (a cycle of length \(n\)). The reviewer posed the problem of finding a direct one to one correspondance between \(A_ n\) and \(B_ n\). \textit{P. Moszkowski} solved that problem, see [Eur. J. Comb. 10, 13-16 (1989; Zbl 0672.05022)]. The present authors also derived such a one to one mapping in straightforward manner.
0 references
labelled trees
0 references