Labelled trees and factorizations of a cycle into transpositions
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.
- Factorizations of cycles and multi-noded rooted trees
- Tree-like properties of cycle factorizations
- Bijection between trees in Stanley character formula and factorizations of a cycle
- The L(2,1)-labelling of trees
- Factoring, into edge transposition of a tree, permutations fixing a terminal vertex
- Trees, parking functions and factorizations of full cycles
- Enumeration of labelled \((k,m)\)-trees
- Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity
- Finitely labeled generating trees and restricted permutations
- A REFINED ENUMERATION OF p-ARY LABELED TREES
- A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
- Labelled trees and pairs of input--output permutations in priority queues
- Transitive cycle factorizations and prime parking functions
- Enumeration of planar constellations
- Tree-like properties of cycle factorizations
- Permutations as minimal powers of a single-cycle class-sum
- Degrees in random uniform minimal factorizations
- Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
- The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
- Factorizations of cycles and multi-noded rooted trees
- The number of prefixes of minimal factorisations of a cycle
- scientific article; zbMATH DE number 3906515 (Why is no real title available?)
- A Differential Operator for Symmetric Functions and the Combinatorics of Multiplying Transpositions
- scientific article; zbMATH DE number 1504579 (Why is no real title available?)
- Toric promotion
- Random stable-type minimal factorizations of the \(n\)-cycle
- A combinatorial interpretation of the bijection of Goulden and Yong
- Trajectories in random minimal transposition factorizations
- Labelled trees and pairs of input-output permutations in priority queues
- Enumeration of a family of set partitions and tree-like structures
- Chords, trees and permutations
This page was built for publication: Labelled trees and factorizations of a cycle into transpositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366027)
