A combinatorial bijection on k-noncrossing partitions

Abstract: For any integer

k g e q 2

, we prove combinatorially the following Euler (binomial) transformation identity

NC_{n+1}^{(k)}(t)=tsum_{i=0}^n{nchoose i}NW_{i}^{(k)}(t),

where

N C_{m}^{(k)} (t)

(resp.~

N W_{m}^{(k)} (t)

) is the sum of weights,

t^{e} x t n u m b e r o f b l o c k s

, of partitions of

1, l d o t s, 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.

This page was built for publication: A combinatorial bijection on $k$-noncrossing partitions