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.     

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

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.     

List colouring of graphs and generalized Dyck paths

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V\left(G\right)\to N$ is a mapping. For a nonnegative integer $m$, let $f^{\left(m\right)}$ be the extension of $f$ to the graph $G$

 $\overline{K_m}$ for which $f^{\left(m\right)}\left(v\right)=\left|V\left(G\right)\right|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-paintable. We study the parameter $m_c(K_n,f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$, an $\overrightarrow{x}$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $a\times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i\le x_{j+1}$. Let $\psi \left(\overrightarrow{x}\right)$ be the number of $\overrightarrow{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $\psi \left((0,1,\dots ,n?1)\right)$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f\left(v_1\right)\le f\left(v_2\right)\le \dots \le f\left(v_n\right)$, then $m_c(G,f)=m_p(G,f)=\psi \left(\overrightarrow{x}\left(f\right)\right)$, where $\overrightarrow{x}\left(f\right)=(x_1,x_2,\dots ,x_n)$ and $x_i=f\left(v_i\right)?i$ for $i=1,2,\dots ,n$. Therefore, if $f\left(v_i\right)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$. We also show that if $G=G_1\cup G_2\cup ?\cup G_p$ is the disjoint union of graphs $G_1,G_2,\dots ,G_p$ and $f=f_1\cup f_2\cup ?\cup f_p$, then $m_c(G,f)={\prod }_{i=1}^p{m}_c(G_i,f_i)$ and $m_p(G,f)={\prod }_{i=1}^p{m}_p(G_i,f_i)$. This generalizes a result in Carraher et al. (2014), where the case each $G_i$ is a copy of $K_1$ is considered.     

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.     

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.     

Enumeration of strings in Dyck paths: A bijective approach

The statistics concerning the number of appearances of a string τ in Dyck paths as well as its appearances in odd and even level have been studied extensively by several authors using mostly algebraic methods. In this work a different, bijective approach is followed giving some known as well as some new results.     

Exchange relations, Dyck paths and copolymer adsorption

We consider a lattice model of fully directed copolymer adsorption equivalent to the enumeration of vertex-coloured Dyck paths. For two infinite families of periodic colourings we are able to solve the model exactly using a type of symmetry we call an exchange relation. For one of these families we are able to find an asymptotic expression for the location of the critical adsorption point as a function of the period of the colouring. This expression describes the effect of a regular inhomogeneity in the polymer on the adsorption transition.     

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.     

Indecomposable permutations, hypermaps and labeled Dyck paths

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered.     

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

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.     

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.     

Asymptotic behavior and the moderate deviation principle for the maximum of a Dyck path

In this work, we obtain a large and moderate deviation principle for the law of the maximum of a random Dyck path. Our result extends the results of Chung (1976), Kennedy (1976) and Khorunzhiy and Marckert (2009).     

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.     

Lattice paths and the q-ballot polynomials

Two statistics with respect to “upper-corners” and “lower-corners” are introduced for lattice paths. The corresponding refined generating functions are shown to be closely related to the q-ballot polynomials that extend the well-known Narayana polynomials and Catalan numbers.