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.     

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.     

Enumerating Motzkin–Rabin geometries

The main result of this paper is an enumeration of all Motzkin‐Rabin geometries on up to 18 points. A Motzkin‐Rabin geometry is a two‐colored linear space with no monochromatic line. We also study the embeddings of Motzkin‐Robin geometries into projective spaces over fields and division rings. We find no Motzkin‐Rabin geometries on up to 18 points embeddable in ?² or ??₂(t)². We find many examples of Motzkin‐Rabin geometries with no proper linear subspaces. We give an example of a proper linear space embeddable in ?(?( )²). © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 179–194, 2007     

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.     

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.     

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.     

Relative locations of subwords in free operated semigroups and Motzkin words

Bracketed words are basic structures both in mathematics (such as Rota-Baxter algebras) and mathematical physics (such as rooted trees) where the locations of the substructures are important. In this paper, we give the classification of the relative locations of two bracketed subwords of a bracketed word in an operated semigroup into the separated, nested, and intersecting cases. We achieve this by establishing a correspondence between relative locations of bracketed words and those of words by applying the concept of Motzkin words which are the algebraic forms of Motzkin paths.     

Motzkin’s theorem of the alternative: a continuous-time generalization

We revisit Zalmai’s theorem, which is a partial generalization of Motzkin’s theorem of the alternative in the continuous-time setting. In particular, we provide two simple examples demonstrating that its existing proof is incorrect, and we demonstrate that a suitably modified variant of Zalmai’s theorem, concerned with the inconsistency of systems of convex inequalities and affine equalities, can be verified. We also derive two generalized variants of Motzkin’s theorem of the alternative in the continuous-time setting.     

A direct method for evaluating some nice Hankel determinants and proofs of several conjectures

In this paper, we propose a direct method to evaluate Hankel determinants for some generating functions satisfying a certain type of quadratic equations, which cover generating functions of Catalan numbers, Motzkin numbers and Schröder numbers. Additionally, four recent conjectures proposed by Cigler (2011) [3] are proved.     

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

Motzkin树上的保护点的计数问题

In this paper,we enumerate the set of Motzkin trees with n edges according to the number of leaves,the number of vertices adjacent to a leaf,the number of protected nodes,the number of(protected)branch nodes,and the number of(protected)lonely nodes.Explicit formulae as well as generating functions are obtained.We also find that,as n goes to infinity,the proportion of protected branch nodes and protected lonely nodes among all vertices of Motzkin trees with n edges approaches 4/27 and 2/9.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

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.     

Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes

Motivated by a recent Basu–Martin–Ryan paper, we obtain a reduced primal-dual pair of a linear semi-infinite programming problem by applying an amended Fourier–Motzkin elimination method to the linear semi-infinite inequality system. The reduced primal-dual pair is equivalent to the original one in terms of consistency, optimal values and asymptotic consistency. Working with this reduced pair and reformulating a linear semi-infinite programme as a linear programme over a convex cone, we reproduce all the theorems that lead to the full eleven possible duality state classification theory. Establishing classification results with the Fourier–Motzkin method means that the two classification theorems for linear semi-infinite programming, 1969 and 1974, have been proved by new and exciting methods. We also show in this paper that the approach to study linear semi-infinite programming using Fourier–Motzkin elimination is not purely algebraic, it is mixed algebraic-analysis.     

Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration

Mathematical Programming - Randomized Kaczmarz, Motzkin Method and Sampling Kaczmarz Motzkin (SKM) algorithms are commonly used iterative techniques for solving a system of linear inequalities...     

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

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

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.     

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.     

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.     

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.