Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Labelled trees and factorizations of a cycle into transpositions - MaRDI portal

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