Identities from weighted Motzkin paths

Based on a weighted version of the bijection between Dyck paths and 2-Motzkin paths, we find combinatorial interpretations of two identities related to the Narayana polynomials and the Catalan numbers. These interpretations answer two questions posed recently by Coker.     

Bijections on two variations of noncrossing partitions

We find bijections on 2-distant noncrossing partitions, 12312-avoiding partitions, 3-Motzkin paths, UH-free Schröder paths and Schröder paths without peaks at even height. We also give a direct bijection between 2-distant noncrossing partitions and 12312-avoiding partitions.     

Skew Motzkin paths

In this paper, we study the class S of skew Motzkin paths, i.e., of those lattice paths that are in the first quadrat, which begin at the origin, end on the x-axis, consist of up steps U =(1, 1),down steps D =(1,-1), horizontal steps H =(1, 0), and left steps L =(-1,-1), and such that up steps never overlap with left steps. Let S_n be the set of all skew Motzkin paths of length n and let 8_n = |S_n|. Firstly we derive a counting formula, a recurrence and a convolution formula for sequence{8_n}n≥0. Then we present several involutions on S_n and consider the number of their fixed points.Finally we consider the enumeration of some statistics on S_n.     

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.     

A partial order on Motzkin paths

The Tamari lattice, defined on Catalan objects such as binary trees and Dyck paths, is a well-studied poset in combinatorics. It is thus natural to try to extend it to other families of lattice paths. In this article, we fathom such a possibility by defining and studying an analogy of the Tamari lattice on Motzkin paths. While our generalization is not a lattice, each of its connected components is isomorphic to an interval in the classical Tamari lattice. With this structural result, we proceed to the enumeration of components and intervals in the poset of Motzkin paths we defined. We also extend the structural and enumerative results to Schröder paths. We conclude by a discussion on the relation between our work and that of Baril and Pallo (2014).     

Some matrix identities on colored Motzkin paths

Merlini and Sprugnoli (2017) give both an algebraic and a combinatorial proof for an identity proposed by Louis Shapiro by using Riordan arrays and a particular model of lattice paths. In this paper, we revisit the identity and emphasize the use of colored partial Motzkin paths as appropriate tool. By using colored Motzkin paths with weight defined according to the height of its last point, we can generalize the identity in several ways. These identities allow us to move from Fibonacci polynomials, Lucas polynomials, and Chebyshev polynomials, to the polynomials of the form ${(z+b)}^n$.     

Counting humps and peaks in generalized Motzkin paths

Let us call a lattice path in $\mathbb{Z}\times \mathbb{Z}$ from $(0,0)$ to $(n,0)$ using $U=(1,k)$, $D=(1,?1)$, and $H=(a,0)$ steps and never going below the $x$-axis, a $(k,a)$-path (of order $n$). A super   $(k,a)$-path is a $(k,a)$-path which is permitted to go below the $x$-axis. We relate the total number of humps in all of the $(k,a)$-paths of order $n$ to the number of super $(k,a)$-paths, where a hump is defined to be a sequence of steps of the form $U{H}^{i}D$, $i\ge 0$. This generalizes recent results concerning the cases when $k=1$ and $a=1$ or $a=\infty$. A similar relation may be given involving peaks (consecutive steps of the form $UD$).     

Some identities on the Catalan, Motzkin and Schröder numbers

In this paper, some identities between the Catalan, Motzkin and Schröder numbers are obtained by using the Riordan group. We also present two combinatorial proofs for an identity related to the Catalan numbers with the Motzkin numbers and an identity related to the Schröder numbers with the Motzkin numbers, respectively.     

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.     

Limits of areas under lattice paths

We consider sequences of polynomials which count lattice paths by area. In some cases the reversed polynomials approach a formal power series as the length of the paths tend to infinity. We find the limiting series for generalized Schröder, Motzkin, and Catalan paths. The limiting series for Schröder paths and their generalizations are shown to count partitions with restrictions on the multiplicities of odd parts and no restrictions on even parts. The limiting series for generalized Motzkin and Catalan paths are shown to count generalized Frobenius partitions and some related arrays.     

Enumerations of peaks and valleys on non-decreasing Dyck paths

A valley in a Dyck path is a local minimum, and a peak is a local maximum. A Dyck path is non-decreasing if the $y$-coordinates of the valleys of the path valley form anon-decreasing sequence. In this paper we provide some statistics about peaks and valleys in non-decreasing Dyck paths, such as their total number, the number of low and high valleys, low and high peaks, etc. Our methods include bijective proofs, recursive relations, and the symbolic method for generating functions.     

A new statistic on Dyck paths for counting 3-dimensional Catalan words

A 3-dimensional Catalan word is a word on three letters so that the subword on any two letters is a Dyck path. For a given Dyck path D, a recently defined statistic counts the number of Catalan words with the property that any subword on two letters is exactly D. In this paper, we enumerate Dyck paths with this statistic equal to certain values, including all primes. The formulas obtained are in terms of Motzkin numbers and Motzkin ballot numbers.     

Symmetric Schröder paths and restricted involutions

Let A_k be the set of permutations in the symmetric group S_k with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns A_k. We present a bijection between symmetric Schröder paths of length 2n and involutions of length n+1 avoiding A₄. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schröder path of a particular type. For each k≥3 we determine the generating function for the number of involutions avoiding the subsequences in A_k, according to length, first entry and number of fixed points.     

Inversion polynomials for 321-avoiding permutations

We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formula for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions.     

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.     

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing 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.     

A simple algorithm for expanding a power series as a continued fraction

I present and discuss an extremely simple algorithm for expanding a formal power series as a continued fraction. This algorithm, which goes back to Euler (1746) and Viscovatov (1805), deserves to be better known. I also discuss the connection of this algorithm with the work of Gauss (1812), Stieltjes (1889), Rogers (1907) and Ramanujan, and a combinatorial interpretation based on the work of Flajolet (1980).