Refinements of two identities on (n,m)-Dyck paths

Abstract: For integers

n, m

with

n g e q 1

and

0 l e q m l e q n

, an

(n, m)

-Dyck path is a lattice path in the integer lattice

m a t h b b Z i m e s m a t h b b Z

using up steps

(0, 1)

and down steps

(1, 0)

that goes from the origin

(0, 0)

to the point

(n, n)

and contains exactly

m

up steps below the line

y = x

. The classical Chung-Feller theorem says that the total number of

(n, m)

-Dyck path is independent of

m

and is equal to the

n

-th Catalan number

C_{n} = f r a c 1 n + 1 2 n c h o o s e n

. For any integer

k

with

1 l e q k l e q n

, let

p_{n, m, k}

be the total number of

(n, m)

-Dyck paths with

k

peaks. Ma and Yeh proved that

p_{n, m, k}

=

p_{n, n - m, n - k}

for

0 l e q m l e q n

, and

p_{n, m, k} + p_{n, m, n - k} = p_{n, m + 1, k} + p_{n, m + 1, n - k}

for

1 l e q m l e q n - 2

. In this paper we give bijective proofs of these two results. Using our bijections, we also get refined enumeration results on the numbers

p_{n, m, k}

and

p_{n, m, k} + p_{n, m, n - k}

according to the starting and ending steps.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Refinements of two identities on \((n,m)\)-Dyck paths