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

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.     

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.     

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.     

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

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.     

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 strings in Dyck paths

This paper deals with the enumeration of Dyck paths according to the statistic “number of occurrences of τ”, for an arbitrary string τ. In this direction, the statistic “number of occurrences of τ at height j” is considered. It is shown that the corresponding generating function can be evaluated with the aid of Chebyshev polynomials of the second kind. This is applied to every string of length 4. Further results are obtained for the statistic “number of occurrences of τ at even (or odd) height”.     

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

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

Counting curves via lattice paths in polygons

This Note presents a formula for the enumerative invariants of arbitrary genus in toric surfaces. The formula computes the number of curves of a given genus through a collection of generic points in the surface. The answer is given in terms of certain lattice paths in the relevant Newton polygon. If the toric surface is $\text{P}{}^2$ or $\text{P}{}^1\text{×}\text{P}{}^1$ then the invariants under consideration coincide with the Gromov–Witten invariants. The formula gives a new count even in these cases, where other computational techniques are available. To cite this article: G. Mikhalkin, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

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.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

Counting lattice chains and Delannoy paths in higher dimensions

Lattice chains and Delannoy paths represent two different ways to progress through a lattice. We use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in a lattice of arbitrary finite dimension. Specifically, fix nonnegative integers n₁,…,n_d, and let L denote the lattice of points (a₁,…,a_d)∈Z^d that satisfy 0≤a_i≤n_i for 1≤i≤d. We prove that the number of chains in L is given by where . We also show that the number of Delannoy paths in L equals Setting n_i=n (for all i) in these expressions yields a new proof of a recent result of Duchi and Sulanke [9] relating the total number of chains to the central Delannoy numbers. We also give a novel derivation of the generating functions for these numbers in arbitrary dimension.     

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.