Linked partitions and linked cycles

DOI10.1016/J.EJC.2007.06.022zbMATH Open1206.05021arXivmath/0607719OpenAlexW2010456256MaRDI QIDQ932823FDOQ932823

Authors: William Y. C. Chen, Susan Y. J. Wu, Catherine Yan 

Publication date: 11 July 2008

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

Abstract: The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schroder number $r_n$, which counts the number of Schroder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.

Full work available at URL: https://arxiv.org/abs/math/0607719

Recommendations

• Noncrossing linked partitions and large \((3,2)\)-Motzkin paths
• Linked partitions and permutation tableaux
• Singly covered minimal elements of linked partitions and cycles of permutations
• Non-crossing linked partitions, the partial order ≪ on 𝑁𝐶(𝑛), and the 𝑆-transform
• Some properties of crossings and partitions

zbMATH Keywords

bijective proofnoncrossing linked partitionlinked cycleSchroeder numberSchroeder paths

Mathematics Subject Classification ID

Partitions of sets (05A18)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Noncrossing Partitions in Surprising Locations
• Crossings and nestings of matchings and partitions
• Multilinear function series and transforms in free probability theory
• Title not available (Why is that?)

Cited In (17)

• Positive and negative chains in charged moon polyominoes
• Chains of length 2 in fillings of layer polyominoes
• Linked partitions and permutation tableaux
• Bijective enumeration of general stacks
• Avoiding monotone chains in fillings of layer polyominoes
• Singly covered minimal elements of linked partitions and cycles of permutations
• Ascents and descents in 01-fillings of moon polyominoes
• Noncrossing linked partitions and large \((3,2)\)-Motzkin paths
• Non-crossing linked partitions, the partial order ≪ on 𝑁𝐶(𝑛), and the 𝑆-transform
• Major index for 01-fillings of moon polyominoes
• Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes
• Remarks on a free analogue of the beta prime distribution
• Vacillating Hecke tableaux and linked partitions
• The parity of the number of permutation tableaux in a fixed shape
• Monobrick, a uniform approach to torsion-free classes and wide subcategories
• Wave linked partitions and 312-avoiding permutations with primacy being 1
• A semi-bijective algorithm for saturated extended 2-regular simple stacks

Uses Software

• OEIS

This page was built for publication: Linked partitions and linked cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q932823)