The cycle lemma and some applications

DOI10.1016/S0195-6698(13)80053-4zbMath0715.05004OpenAlexW2090215490WikidataQ106200385 ScholiaQ106200385MaRDI QIDQ751658

Nachum Dershowitz, Shmuel Zaks

Publication date: 1990

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(13)80053-4

zbMATH Keywords

treecycle lemmaforestscyclic permutationsaverage heightdominating sequences

Mathematics Subject Classification ID

Trees (05C05) Permutations, words, matrices (05A05)

Related Items (32)

A parallel algorithm for the generation of a permutation and applications ⋮ On the combinatorics of derangements and related permutations ⋮ The Corners of Core Partitions ⋮ Bijections for faces of the Shi and Catalan arrangements ⋮ Combinatorics of diagonally convex directed polyominoes ⋮ Enumeration of connected Catalan objects by type ⋮ Down-step statistics in generalized Dyck paths ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ Scaling limits of slim and fat trees ⋮ Lattice path moments by cut and paste ⋮ On directed lattice paths with vertical steps ⋮ Generic classification and asymptotic enumeration of dope matrices ⋮ The non-commutative cycle lemma ⋮ The butterfly decomposition of plane trees ⋮ Lagrange inversion and Schur functions ⋮ Multivariate Fuss-Catalan numbers ⋮ A linear-time algorithm for the generation of trees ⋮ Bounded affine permutations I. Pattern avoidance and enumeration ⋮ A symmetric variation of a distribution of Kreweras and Poupard ⋮ Controlled non-uniform random generation of decomposable structures ⋮ An equipartition property for the distribution of multiset permutation inversions ⋮ Patterns in trees ⋮ Raney and Catalan ⋮ On 1-factorizations of bipartite Kneser graphs ⋮ A cyclic approach on classical ruin model ⋮ Partitions of \(\mathbb Z_n\) into arithmetic progressions ⋮ Infinite Sperner's theorem ⋮ Building uniformly random subtrees ⋮ Refined Chung-Feller theorems for lattice paths ⋮ Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs ⋮ Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers ⋮ The Bohnenblust-Spitzer algorithm and its applications

Cites Work

• A combinatorial proof of the multivariable Lagrange inversion formula
• The average height of binary trees and other simple trees
• Terms and cyclic permutations
• On generalised Catalan numbers
• A problem of arrangements
• A Combinatorial Lemma and Its Application to Probability Theory
• A transformation on ordered trees
• On the Altitude of Nodes in Random Trees
• An Elementary Evaluation of the Catalan Numbers
• Some Aspects of the Random Sequence
• Functional Composition Patterns and Power Series Reversion
• Some Word-Problems
• Correspondences between plane trees and binary sequences
• Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The cycle lemma and some applications