Labelled trees and factorizations of a cycle into transpositions (Q2366027)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 223120
Language Label Description Also known as
default for all languages
No label defined
    English
    Labelled trees and factorizations of a cycle into transpositions
    scientific article; zbMATH DE number 223120

      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