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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references