2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.     

On the combinatorics of the Pfaff identity

Recently, there has been a revival of interest in the Pfaff identity on hypergeometric series because of the specialization of Simons and a generalization of Munarini. We present combinatorial settings and interpretations of the specialization and the generalization; one is based on free Dyck paths and free Schröder paths, and the other relies on a correspondence of Foata and Labelle between the Meixner endofunctions and bicolored permutations, and an extension of the technique developed by Labelle and Yeh for the Pfaff identity. Applying the involution on weighted Schröder paths, we derive a formula for the Narayana numbers as an alternating sum of the Catalan numbers.     

Some combinatorial interpretations ofq-analogs of Schröder numbers

We introduce two definitions of Schröder numberq-analogs and show some combinatorial interpretations of theseq-numbers. We use the following combinatorial objects for these interpretations: Schröder paths, 1-colored parallelogram polyominoes and permutations with forbidden subsequences (4231, 4132). We enumerate these objects according to various parameters by means of a recentq-counting technique. We prove that the firstq-Schröder number enumerates of Schröder paths with respect to area and the number of permutation inversions, while the second one counts the 1-colored parallelogram polyominoes according to their width and area. Finally, we illustrate some relations among the parameters characterizing the combinatorial objects.     

A bijection between ordered trees and 2-Motzkin paths and its many consequences

A new bijection between ordered trees and 2-Motzkin paths is presented, together with its numerous consequences regarding ordered trees as well as other combinatorial structures such as Dyck paths, bushes, {0,1,2}-trees, Schröder paths, RNA secondary structures, noncrossing partitions, Fine paths, and Davenport-Schinzel sequences.RésuméUne nouvelle bijection entre arbres ordonnés et chemins de Motzkin bicolorés est présentée, avec ses nombreuses conséquences en ce qui concerne les arbres ordonnés ainsi que d'autres structures combinatoires telles que chemins de Dyck, buissons, arbres de type {0,1,2}, chemins de Schröder, structures secondaires de type RNA, partitions non croisées, chemins de Fine, et enfin suites de Davenport-Schinzel.     

Refined Chung-Feller theorems for lattice paths

In this paper we prove a strengthening of the classical Chung-Feller theorem and a weighted version for Schröder paths. Both results are proved by refined bijections which are developed from the study of Taylor expansions of generating functions. By the same technique, we establish variants of the bijections for Catalan paths of order d and certain families of Motzkin paths. Moreover, we obtain a neat formula for enumerating Schröder paths with flaws.     

Laurent biorthogonal polynomials, q-Narayana polynomials and domino tilings of the Aztec diamonds

A Toeplitz determinant whose entries are described by a q-analogue of the Narayana polynomials is evaluated by means of Laurent biorthogonal polynomials which allow of a combinatorial interpretation in terms of Schröder paths. As an application, a new proof is given to the Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp concerning domino tilings of the Aztec diamonds. The proof is based on the correspondence with non-intersecting Schröder paths developed by Johansson.     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

Restricted Dumont permutations, Dyck paths, and noncrossing partitions

We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain patterns of length 3 and 4 and give a natural bijection between 3142-avoiding Dumont permutations of the second kind and noncrossing partitions that uses cycle decomposition, as well as bijections between 132-, 231- and 321-avoiding Dumont permutations and Dyck paths. Finally, we enumerate Dumont permutations of the first kind simultaneously avoiding certain pairs of 4-letter patterns and another pattern of arbitrary length.     

Riordan paths and derangements

Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and -avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schröder numbers.     

Linked partitions and linked cycles

The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schröder number r_n, which counts the number of Schröder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.     

Counting Dyck Paths by Area and Rank

The set of Dyck paths of length 2n inherits a lattice structure from a bijection with the set of noncrossing partitions with the usual partial order. In this paper, we study the joint distribution of two statistics for Dyck paths: area (the area under the path) and rank (the rank in the lattice). While area for Dyck paths has been studied, pairing it with this rank function seems new, and we get an interesting (q, t)-refinement of the Catalan numbers. We present two decompositions of the corresponding generating function: One refines an identity of Carlitz and Riordan; the other refines the notion of γ-nonnegativity, and is based on a decomposition of the lattice of noncrossing partitions due to Simion and Ullman. Further, Biane’s correspondence and a result of Stump allow us to conclude that the joint distribution of area and rank for Dyck paths equals the joint distribution of length and reflection length for the permutations lying below the n-cycle (12· · ·n) in the absolute order on the symmetric group.     

Recurrence relations with two indices and even trees

Recently, the author, Mansour, introduced a combinatorial problem, called Hobby's problem, to study different types of recurrence relations with two indices. Moreover, he presented several recurrence relations with two indices related to Dyck paths and Schröder paths. In this paper, we generalize Hobby's problem to study other types of recurrence relations with two indices for which a combinatorial method provides a complete solution. Combinatorially, we describe these recurrence relations as a set of lattice paths in the second octant of the plane integer lattice, and then we map bijectively these lattice paths to the set of even trees. Analytically, we use the kernel method technique to solve these recurrence relations.     

Schröder matrix as inverse of Delannoy matrix

Using Riordan arrays, we introduce a generalized Delannoy matrix by weighted Delannoy numbers. It turns out that Delannoy matrix, Pascal matrix, and Fibonacci matrix are all special cases of the generalized Delannoy matrices, meanwhile Schröder matrix and Catalan matrix also arise in involving inverses of the generalized Delannoy matrices. These connections are the focus of our paper. The half of generalized Delannoy matrix is also considered. In addition, we obtain a combinatorial interpretation for the generalized Fibonacci numbers.     

Two bijections for the area of Dyck paths

The sum of the areas of (2n+2)-length Dyck paths, or total area, is equal to the number of points with ordinate 1 in Grand-Dyck paths of length 2n+2, n⩾0. A bijective proof of this correspondence is shown by passing through an auxiliary class of marked paths. The sequence of numbers 1,6,29,130,562,… counts the total area of (2n+2)-length Dyck paths as well as the number of points having ordinate 0 and which satisfy an additional condition, on 2n-length paths made up of rise and fall steps. First, a bijection between these points and the triangles constituting the total area of (2n+2)-length Dyck paths is established, and then the correspondence between the above-mentioned points and the points with ordinate 1 on (2n+2)-length Grand-Dyck paths is shown.     

Dyck paths and restricted permutations

This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and S_n(321) and S_n(231), respectively. We also discuss permutations in S_n avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.     

Enumerating several aspects of non-decreasing Dyck paths

A Dyck path is non-decreasing if the $y$-coordinates of its valleys form a non-decreasing sequence. In this paper we give enumerative results and some statistics of several aspects of non-decreasing Dyck paths. We give the number of pyramids at a fixed level that the paths of a given length have, count the number of primitive paths, count how many of the non-primitive paths can be expressed as a product of primitive paths, and count the number of paths of a given height and a given length. We present and prove our results using combinatorial arguments, generating functions (using the symbolic method) and parameterize the results studied here using the Riordan arrays. We use known bijections to connect direct column-convex polyominoes, Elena trees, and non-decreasing Dyck paths.     

Lattice paths and generalized cluster complexes

In this paper we propose a variant of the generalized Schröder paths and generalized Delannoy paths by giving a restriction on the positions of certain steps. This generalization turns out to be reasonable, as attested by the connection with the faces of generalized cluster complexes of types A and B. As a result, we derive Krattenthaler's F-triangles for these two types by a combinatorial approach in terms of lattice paths.     

Enumeration of multi-colored rooted maps

We present a study of n-colored rooted maps in orientable and locally orientable surfaces. As far as we know, no work on these maps has yet been published. We give a system of n functional equations satisfied by n-colored orientable rooted maps regardless of genus and with respect to edges and vertices. We exhibit the solution of this system as a vector where each component has a continued fraction form and we deduce a new equation generalizing the Dyck equation for rooted planar trees. Similar results are shown for n-colored rooted maps in locally orientable surfaces.     

Oscillating rim hook tableaux and colored matchings

We find a correspondence between oscillating m-rim hook tableaux and m-colored matchings, where m is a positive integer. An oscillating m  -rim hook tableau is defined as a sequence (λ⁰,λ¹,…,λ2n)$({\lambda }^0,{\lambda }^1,\dots ,{\lambda }^{2n})$ of Young diagrams starting with the empty shape and ending with the empty shape such that λi${\lambda }^i$ is obtained from λi−1${\lambda }^{i-1}$ by adding an m-rim hook or by deleting an m-rim hook. Our bijection relies on the generalized Schensted algorithm due to White. An oscillating 2-rim hook tableau is also called an oscillating domino tableau. When we restrict our attention to two column oscillating domino tableaux of length 2n  , we are led to a bijection between such tableaux and noncrossing 2-colored matchings on {1,2,…,2n}$\{1,2,\dots ,2n\}$, which are counted by the product CnC_n+1$C_n{C}_{n+1}$ of two consecutive Catalan numbers. A 2-colored matching is noncrossing if there are no two arcs of the same color that are intersecting. We show that oscillating domino tableaux with at most two columns are in one-to-one correspondence with Dyck path packings. A Dyck path packing of length 2n   is a pair (D,E)$(D,E)$, where D is a Dyck path of length 2n, and E is a dispersed Dyck path of length 2n that is weakly covered by D. So we deduce that Dyck path packings of length 2n   are counted by CnC_n+1$C_n{C}_{n+1}$.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.