Restricting Dyck Paths and 312-Avoiding Permutations

Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani Dipartimento di Matematica e Informatica “Ulisse Dini” Università di Firenze Viale G. B. Morgagni 65, 50134 Firenze, Italy

                    elena.barcucci@unifi.it
                   antonio.bernini@unifi.it
                   stefano.bilotta@unifi.it
                    renzo.pinzani@unifi.it

Abstract

We interpret Dyck paths of height at most h and without valleys at height h − 1 combinatorially, by means of 312-avoding permutations with some restrictions on their left-to-right maxima. We obtain our results by analyzing a restriction of a well-known bijection between the sets of Dyck paths and 312-avoding permutations. We also provide a recursive formula enumerating these two structures by using the ECO method and the theory of production matrices. As a further result we obtain a family of combinatorial identities involving Catalan numbers.

1 Introduction

Dyck paths have been widely used in several combinatorial applications. Here, we only recall their involvement in theory of codes [?, ?], cryptography [?] and partially ordered structures [?]. Dyck path enumeration has also received much attention in recent decades. An interesting paper dealing with this matter is the one by Deutsch [?] where the author enumerates Dyck paths according to various parameters.

A subclass of these paths has been considered thanks to the simple behaviour of the recursive relations describing them and the rational nature of the related generating function. More precisely, the generating function associated with Dyck paths is algebraic, and it is rational when the paths are bounded [?, ?], for example with respect to the height. Kallipoliti et al. [?] consider Dyck paths of height less or equal to a precise value k. Moreover, in the same paper a further restriction is considered: the authors analyze some characteristics of Dyck paths avoiding valleys at specified height.

In our work, we consider Dyck paths of height equal or less than h and with no valley at height h − 1. We obtain an interesting relation with a subclass of 312-avoiding permutations (actually, we obtain a bijection) having some constraints on the left-to-right maxima.

The paper structure is the following. In Section 2 some preliminaries on Dyck paths and pattern avoiding permutations are introduced and moreover we recall a well-known bijection between the sets of Dyck paths and 312-avoiding permutations. We are going to largely use this bijection in the whole paper. Section ?? and Section ?? are devoted to the generation of the considered Dyck paths (of height equal or less than h and with no valley at height h − 1) and the corresponding 312-avoiding permutations with some restriction on their left to right maxima. The enumerative results are presented in Section ??. We provide the generating functions for the above mentioned classes and a recurrence relation for their enumeration according to their size.

Finally, we conclude the paper proposing some further developments on the present topics.

2 Preliminaries

A Dyck path is a lattice path in the discrete plane ℤ^{2} from (0, 0) to (2n, 0) with up and down steps in {(1, 1), (1, −1)}, never crossing the x-axis. The number of up steps in every prefix of a Dyck path is greater or equal to the number of down steps, and the total number of steps (the length of the path) is 2n. We denote the set of Dyck paths of length 2n (or equivalently semilength n) by D_{n}. A Dyck path can be codified by a string over the alphabet {U, D}, where U and D replace the up and down steps, respectively. The empty Dyck path is denoted by ε.

The height of a Dyck path P is the maximum ordinate reached by one of its steps. A valley of P is an occurrence of the substring DU, while a peak is an occurrence of the substring UD. The height of a valley (peak) is the ordinate reached by D (U).

We denote by D_{n}^{(h,k)} the set of Dyck paths having semilength n and height at most h, and avoiding k − 1 consecutive valleys at height h − 1. The set of Dyck paths having semilength n with height at most h (without restriction on the number of valleys) is denoted by D_{n}^{(h)}. Moreover,

D^{(h)} = ∑_{n≥0} D_{n}^{(h)} and D^{(h,k)} = ∑_{n≥0} D_{n}^{(h,k)}.

The cardinalities of D_{n}^{(h,k)} and D_{n}^{(h)} are indicated by D_{n}^{(h,k)} and D_{n}^{(h)}, respectively. Finally, the set D_{n} of unrestricted Dyck paths having semilength n ≥ 0 is enumerated by the n-Catalan number

C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

When k = 2, the set D_{n}^{(h,2)} represents the set of Dyck paths with height at most h and without valleys at height h−1. In the present work we describe a combinatorial interpretation