Dyck paths with a first return decomposition constrained by height

We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height $k$ with a flat (resp. with no flats) at the maximal height.     

Pattern-restricted permutations composed of 3-cycles

In this paper, we characterize and enumerate pattern-avoiding permutations composed of only 3-cycles. In particular, we answer the question for the six patterns of length 3. We find that the number of permutations composed of n 3-cycles that avoid the pattern 231 (equivalently 312) is given by $3^{n?1}$, while the generating function for the number of those that avoid the pattern 132 (equivalently 213) is given by a formula involving the generating functions for the well-known Motzkin numbers and Catalan numbers. The number of permutations composed of n 3-cycles that avoid the pattern 321 is characterized by a weighted sum involving statistics on Dyck paths of semilength n.     

Potential polynomials and Motzkin paths

A Motzkin path of length n is a lattice path from (0,0) to (n,0) in the plane integer lattice Z×Z consisting of horizontal-steps (1,0), up-steps (1,1), and down-steps (1,−1), which never passes below the x-axis. A u-segment (resp. h-segment) of a Motzkin path is a maximal sequence of consecutive up-steps (resp. horizontal-steps). The present paper studies two kinds of statistics on Motzkin paths: “number of u-segments” and “number of h-segments”. The Lagrange inversion formula is utilized to represent the weighted generating function for the number of Motzkin paths according to the two statistics as a sum of the partial Bell polynomials or the potential polynomials. As an application, a general framework for studying compositions are also provided.     

Knight's paths towards Catalan numbers

We provide enumerating results for partial knight's paths of a given size. We prove algebraically that zigzag knight's paths of a given size ending on the x-axis are enumerated by the generalized Catalan numbers, and we give a constructive bijection with peakless Motzkin paths of a given length. After enumerating partial knight's paths of a given length, we prove that zigzag knight's paths of a given length ending on the x-axis are counted by the Catalan numbers. Finally, we give a constructive bijection with Dyck paths of a given length.     

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.     

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.     

Standard Young tableaux and colored Motzkin paths

In this paper, we propose a notion of colored Motzkin paths and establish a bijection between the n-cell standard Young tableaux (SYT) of bounded height and the colored Motzkin paths of length n. This result not only gives a lattice path interpretation of the standard Young tableaux but also reveals an unexpected intrinsic relation between the set of SYTs with at most $2d+1$ rows and the set of SYTs with at most 2d rows.     

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.     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

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).     

A note on 2-distant noncrossing partitions and weighted Motzkin paths

We prove a conjecture of Drake and Kim: the number of 2-distant noncrossing partitions of {1,2,…,n} is equal to the sum of weights of Motzkin paths of length n, where the weight of a Motzkin path is a product of certain fractions involving Fibonacci numbers. We provide two proofs of their conjecture: one uses continued fractions and the other is combinatorial.     

峰严格递增的Dyck路的计数

本文考虑了由最高峰的高度为m,并且峰的高度沿着Dyck路严格递增的所有Dyck路组成的集合,即集合Dm的子集的计数问题．利用双射、生成树以及Riordan阵的方法来对集合Dm的一些子集进行计数,得到了一些以经典的序列如Catalan数、Narayana数、Motzkin数、Fibonacci数、Schroder数以及第一类无符号Stirling数来计数的组合结构．特别地,我们给出了两个新的Catalan结构,它们并没有明显地出现在Stanley关于Catalan结构的列表中．     

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.     

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.     

On highly palindromic words

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length-a power of the prevalent letter-we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word w by the ratio |rws|/|w|, where the word rws is minimal palindromic and rs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.     

Hankel transforms of generalized Motzkin numbers

We study Hankel transform of the sequences (u,l,d),t, and the classical Motzkin numbers. Using the method based on orthogonal polynomials, we give closed‐form evaluations of the Hankel transform of the aforementioned sequences, sums of two consecutive, and shifted sequences. We also show that these sequences satisfy some interesting convolutional properties. Finally, we partially consider the Hankel transform evaluation of the sums of two consecutive shifted (u,l,d)‐Motzkin numbers. Copyright © 2017 John Wiley & Sons, Ltd.     

Motzkin numbers

Two equations relate the well-known Catalan numbers with the relatively unknown Motzkin numbers which suggest that the combinatorial settings of the Catalan numbers should also yield Motzkin numbers. In this paper we provide a representative selection of 14 situations where the Motzkin numbers occur along with the Catalan numbers.     

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.     

Riordan 矩阵在广义 Motzkin 路计数中的应用

用Riordan矩阵的方法研究了具有4种步型的加权格路(广义Motzkin路)的计数问题,引入了一类新的计数矩阵,即广义Motzkin矩阵.同时给出了这类矩阵的Riordan表示,也得到了广义Motzkin路的计数公式.Catalan矩阵,Schrder矩阵和Motzkin矩阵都是广义Motzkin矩阵的特殊情形.