A combinatorial bijection on k-noncrossing partitions

2019/05/25 by Zhicong Lin, Lin, Zhicong, Dongsu Kim +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1905.10526

20 pages, 20 figures, presented by Dongsu Kim in 2018 (January 10) JMM Special Session in honor of Dennis Stanton

arxiv created 2019/09/16 · arxiv updated 2019/09/17

Abstract

For any integer k≥2, we prove combinatorially the following Euler (binomial) transformation identity \NC_n+1^(k)(t)=t∑_i=0ⁿn\choose i\NW_i^(k)(t), where \NC_m^(k)(t) (resp.~\NW_m^(k)(t)) is the sum of weights, tⁿumber of blocks, of partitions of \1,…,m\ without k-crossings (resp.~enhanced k-crossings). The special k=2 and t=1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k=3 and t=1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically.

Related

• Reduction of m-Regular Noncrossing Partitions
• The sets of flattened partitions with forbidden patterns
• A uniform bijection between nonnesting and noncrossing partitions
• Crossings and Nestings of Matchings and Partitions
• More bijective Catalan combinatorics on permutations and on signed permutations