New identities in the Catalan triangle

In this paper we prove new identities in the Catalan triangle whose (n,p) entry is defined by

     

A Catalan triangle

We develop an arithmetic triangle similar to Pascal's triangle. The entries are interpreted in terms of numbers of pairs of nonintersecting paths in the first quadrant. The main applications are results about the Catalan numbers and various random walk problems.     

A note about the Catalan triangle

A new identity is obtained for the Catalan triangle introduced by Shapiro.     

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.     

Catalan matrix and related combinatorial identities

We introduce the notion of the Catalan matrix whose non-zero elements are expressions which contain the Catalan numbers arranged into a lower triangular Toeplitz matrix. Inverse of the Catalan matrix is derived. Correlations between the matrix and the generalized Pascal matrix are considered. Some combinatorial identities involving Catalan numbers, binomial coefficients and the generalized hypergeometric function are derived using these correlations. Moreover, an additional explicit representation of the Catalan number, as well as an explicit representation of the sum of the first m Catalan numbers are given.     

Factors of binomial sums from the Catalan triangle

By using the Newton interpolation formula, we generalize the recent identities on the Catalan triangle obtained by Miana and Romero as well as those of Chen and Chu. We further study divisibility properties of sums of products of binomial coefficients and an odd power of a natural number. For example, we prove that for all positive integers n₁,…,nm, nm+1=n₁, and any nonnegative integer r, the expression

     

Sums of powers of Catalan triangle numbers

In this paper, we consider combinatorial numbers ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$, mentioned as Catalan triangle numbers where $C_{m,k}?\left(\genfrac{}{}{0ex}{}{m?1}{k}\right)?\left(\genfrac{}{}{0ex}{}{m?1}{k?1}\right)$. These numbers unify the entries of the Catalan triangles $B_{n,k}$ and $A_{n,k}$ for appropriate values of parameters $m$ and $k$, i.e., $B_{n,k}=C_{2n,n?k}$ and $A_{n,k}=C_{2n+1,n+1?k}$. In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers $C_n$ that is $C_{2n,n?1}=C_{2n+1,n}=C_n$.We present identities for sums (and alternating sums) of $C_{m,k}$, squares and cubes of $C_{m,k}$ and, consequently, for $B_{n,k}$ and $A_{n,k}$. In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$ and harmonic numbers ${\left(H_n\right)}_{n\ge 1}$. Finally, in the last section, new open problems and identities involving ${\left(C_n\right)}_{n\ge 0}$ are conjectured.     

Some identities on Catalan numbers and hypergeometric functions via Catalan matrix power

In this paper we use the Catalan matrix power as a tool for deriving identities involving Catalan numbers and hypergeometric functions. For that purpose, we extend earlier investigated relations between the Catalan matrix and the Pascal matrix by inserting the Catalan matrix power and particulary the squared Catalan matrix in those relations. We also pay attention to some relations between Catalan matrix powers of different degrees, which allows us to derive the simplification formula for hypergeometric function ₃F₂, as well as the simplification formula for the product of the Catalan number and the hypergeometric function ₃F₂. Some identities involving Catalan numbers, proved by the non-matrix approach, are also given.     

Proofs of two conjectures on Catalan triangle numbers

We prove two conjectures on sums of products of Catalan triangle numbers, which were originally conjectured by Miana et al. [Discrete Math. 340 (2017), 2388–2397]. The first one is proved by using Zeilberger's algorithm, and the second one is proved by establishing its q-analogue.     

Ballot matrix as Catalan matrix power and related identities

We use an analytical approach to find the kth power of the Catalan matrix. Precisely, it is proven that the power of the Catalan matrix is a lower triangular Toeplitz matrix which contains the well-known ballot numbers. A result from [H. S. Wilf, Generatingfunctionology, Academic Press, New York, 1990, Free download available from http://www.math.upenn.edu/~wilf/Downld.html.], related to the generating function for Catalan numbers, is extended to the negative integers. Three interesting representations for Catalan numbers by means of the binomial coefficients and the hypergeometric functions are obtained using relations between Catalan matrix powers.     

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.     

Categorification of the Catalan monoid

We construct a finitary additive 2-category whose Grothendieck ring is isomorphic to the semigroup algebra of the monoid of order-decreasing and order-preserving transformations of a finite chain.     

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.     

Double Catalan monoids

In this paper, we define and study what we call the double Catalan monoid. This monoid is the image of a natural map from the 0-Hecke monoid to the monoid of binary relations. We show that the double Catalan monoid provides an algebraization of the (combinatorial) set of 4321-avoiding permutations and relate its combinatorics to various off-shoots of both the combinatorics of Catalan numbers and the combinatorics of permutations. In particular, we give an algebraic interpretation of the first derivative of the Kreweras involution on Dyck paths, of 4321-avoiding involutions and of recent results of Barnabei et al. on admissible pairs of Dyck paths. We compute a presentation and determine the minimal dimension of an effective representation for the double Catalan monoid. We also determine the minimal dimension of an effective representation for the 0-Hecke monoid.     

Catalan Numbers for the Classroom?

---

Catalan Numbers for the Classroom?

---