A note on 2-distant noncrossing partitions and weighted Motzkin paths

DOI10.1016/J.DISC.2010.07.017MaRDI QIDQ712276zbMATH OpenOpenAlexFDO

Authors Ira M. Gessel, Jang Soo Kim

Publication date 28 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

continued fractionDyck pathFibonacci numberMotzkin pathSchröder path

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Extremal set theory (05D05)

Abstract: We prove a conjecture of Drake and Kim: the number of $2$-distant noncrossing partitions of $1,2,\mathrm{...},n$ is equal to the sum of weights of Motzkin paths of length $n$, where the weight of a Motzkin path is a product of certain fractions involving Fibonacci numbers. We provide two proofs of their conjecture: one uses continued fractions and the other is combinatorial.

Recommendations

• Bijections from weighted Dyck paths to Schröder paths
• scientific article; zbMATH DE number 2197882
• k-distant crossings and nestings of matchings and partitions
• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions

Cites work

• scientific article; zbMATH DE number 4121470 (Why is no real title available?)
• Enumeration of (k,2)-noncrossing partitions
• Front representation of set partitions
• Schröder paths and pattern avoiding partitions
• k-distant crossings and nestings of matchings and partitions

Cited in

(1)

• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions

This page was built for publication: A note on 2-distant noncrossing partitions and weighted Motzkin paths

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