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.     

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.     

Tripartite Ramsey numbers for paths

In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P_2n+1,P_2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K_3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007     

Further identities on Catalan numbers

Three summation formulae on the $\lambda$-extended Catalan numbers are established by means of hypergeometric series approach with one of them being provided a combinatorial proof through lattice path countings.     

Cumulants, lattice paths, and orthogonal polynomials

A formula expressing free cumulants in terms of Jacobi parameters of the corresponding orthogonal polynomials is derived. It combines Flajolet's theory of continued fractions and the Lagrange inversion formula. For the converse we discuss Gessel–Viennot theory to express Hankel determinants in terms of various cumulants.     

Raney and Catalan

Raney’s lemma is often used in a counting argument to prove the formula for (generalized) Catalan numbers. It ensures the existence of “good” cyclic shifts of certain sequences, i.e. cyclic shifts for which all partial sums are positive.We introduce a simple algorithm that finds these cyclic shifts and also those with a slightly weaker property. Moreover it provides simple proofs of lemma’s of Raney type.A similar clustering procedure is also used in a simple proof of a theorem on probabilities of which many well-known results (e.g. on lattice paths and on generalized Catalan numbers) can be derived as corollaries. The theorem generalizes generalized Catalan numbers. In the end it turns out to be equivalent to a formula of Raney.     

Square -lattice paths and

The combinatorial -Catalan numbers are weighted sums of Dyck paths introduced by J. Haglund and studied extensively by Haglund, Haiman, Garsia, Loehr, and others. The -Catalan numbers, besides having many subtle combinatorial properties, are intimately connected to symmetric functions, algebraic geometry, and Macdonald polynomials. In particular, the 'th -Catalan number is the Hilbert series for the module of diagonal harmonic alternants in variables; it is also the coefficient of in the Schur expansion of . Using -analogues of labelled Dyck paths, Haglund et al. have proposed combinatorial conjectures for the monomial expansion of and the Hilbert series of the diagonal harmonics modules.

This article extends the combinatorial constructions of Haglund et al. to the case of lattice paths contained in squares. We define and study several -analogues of these lattice paths, proving combinatorial facts that closely parallel corresponding results for the -Catalan polynomials. We also conjecture an interpretation of our combinatorial polynomials in terms of the nabla operator. In particular, we conjecture combinatorial formulas for the monomial expansion of , the ``Hilbert series' , and the sign character .

     

Heisenberg characters, unitriangular groups, and Fibonacci numbers

Let Un(Fq) denote the group of unipotent n×n upper triangular matrices over a finite field with q elements. We show that the Heisenberg characters of Un+1(Fq) are indexed by lattice paths from the origin to the line x+y=n using the steps (1,0), (1,1), (0,1), (0,2), which are labeled in a certain way by nonzero elements of Fq. In particular, we prove for n?1 that the number of Heisenberg characters of Un+1(Fq) is a polynomial in q−1 with nonnegative integer coefficients and degree n, whose leading coefficient is the nth Fibonacci number. Similarly, we find that the number of Heisenberg supercharacters of Un(Fq) is a polynomial in q−1 whose coefficients are Delannoy numbers and whose values give a q-analogue for the Pell numbers. By counting the fixed points of the action of a certain group of linear characters, we prove that the numbers of supercharacters, irreducible supercharacters, Heisenberg supercharacters, and Heisenberg characters of the subgroup of Un(Fq) consisting of matrices whose superdiagonal entries sum to zero are likewise all polynomials in q−1 with nonnegative integer coefficients.     

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

一些与Dyck路有关的数的恒等式

本文通过Cauchy留数定理和算子方法导出了一些形如∑_i=0ⁿ (-1)^n-i(n i)U_{m+k+i, k+i} =f(n) 和∑_i=0²ⁿ(-1 )ⁱ(2n i) U_{m+k+i, k+i} = g(n)的差分恒等式,这里U_{n, κ}表示Dyck路在不同条件下的计数公式,f(n),g(n)与m(n)只和n有关的函数.     

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.     

Multiple partitions, lattice paths and a Burge-Bressoud-type correspondence

A bijection is presented between (1): partitions with conditions f_j+f_j+1≤k−1 and f₁≤i−1, where f_j is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n⁽¹⁾,n⁽²⁾,…,n^(k−1)) such that and , where m_j is the number of parts in n^(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence.     

Generalized harmonic numbers,Jacobi numbers and a Hankel determinant evaluation

In this paper we will introduce a sequence of complex numbers that are called the Jacobi numbers. This sequence generalizes in a natural way several sequences that are known in the literature, such as Catalan numbers, central binomial numbers, generalized catalan numbers, the coefficient of the Hilbert matrix and others. Subsequently, using a study of the polynomial of Jacobi, we give an evaluation of the Hankel determinants that associated with the sequence of Jacobi numbers. Finally, by finding a relationship between the Jacobi numbers and generalized harmonic numbers, we determine the evaluation of the Hankel determinants that are associated with generalized harmonic numbers.     

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.     

Hankel determinants of sums of consecutive Motzkin numbers

We use combinatorial methods to evaluate Hankel determinants for the sequence of sums of consecutive t-Motzkin numbers. More specifically, we consider the following determinant:

     

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.