In this paper, we define four transformations on the classical Catalan triangle $mathcal{C}=(C_{n,k})_{ngeq kgeq 0}$ with $C_{n,k}=frac{k+1}{n+1}binom{2n-k}{n}$. The first three ones are based on the determinant and the forth is utilizing the permane
nt of a square matrix. It not only produces many known and new identities involving Catalan numbers, but also provides a new viewpoint on combinatorial triangles.
A partial Motzkin path is a path from $(0, 0)$ to $(n, k)$ in the $XOY$-plane that does not go below the $X$-axis and consists of up steps $U=(1, 1)$, down steps $D=(1, -1)$ and horizontal steps $H=(1, 0)$. A weighted partial Motzkin path is a partia
l Motzkin path with the weight assignment that all up steps and down steps are weighted by 1, the horizontal steps are endowed with a weight $x$ if they are lying on $X$-axis, and endowed with a weight $y$ if they are not lying on $X$-axis. Denote by $M_{n,k}(x, y)$ to be the weight function of all weighted partial Motzkin paths from $(0, 0)$ to $(n, k)$, and $mathcal{M}=(M_{n,k}(x,y))_{ngeq kgeq 0}$ to be the infinite lower triangular matrices. In this paper, we consider the sums of minors of second order of the matrix $mathcal{M}$, and obtain a lot of interesting determinant identities related to $mathcal{M}$, which are proved by bijections using weighted partial Motzkin paths. When the weight parameters $(x, y)$ are specialized, several new identities are obtained related to some classical sequences involving Catalan numbers. Besides, in the alternating cases we also give some new explicit formulas for Catalan numbers.
In this note, using the derangement polynomials and their umbral representation, we give another simple proof of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory.
In this note, by the umbra calculus method, the Sun and Zagiers congruences involving the Bell numbers and the derangement numbers are generalized to the polynomial cases. Some special congruences are also provided.
Recently, Deutsch and Elizalde studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let $A_{n,k}$ denote the number of partitions of ${1,2,dots, n+1}$ with t
he largest singleton ${k+1}$ for $0leq kleq n$. In this paper, several explicit formulas for $A_{n,k}$, involving a Dobinski-type analog, are obtained by algebraic and combinatorial methods, many combinatorial identities involving $A_{n,k}$ and Bell numbers are presented by operator methods, and congruence properties of $A_{n,k}$ are also investigated. It will been showed that the sequences $(A_{n+k,k})_{ngeq 0}$ and $(A_{n+k,k})_{kgeq 0}$ (mod $p$) are periodic for any prime $p$, and contain a string of $p-1$ consecutive zeroes. Moreover their minimum periods are conjectured to be $N_p=frac{p^p-1}{p-1}$ for any prime $p$.
Recently, by the Riordans identity related to tree enumerations, begin{eqnarray*} sum_{k=0}^{n}binom{n}{k}(k+1)!(n+1)^{n-k} &=& (n+1)^{n+1}, end{eqnarray*} Sun and Xu derived another analogous one, begin{eqnarray*} sum_{k=0}^{n}binom{n}{k}D_{k+1}(n+1
)^{n-k} &=& n^{n+1}, end{eqnarray*} where $D_{k}$ is the number of permutations with no fixed points on ${1,2,dots, k}$. In the paper, we utilize the $lambda$-factorials of $n$, defined by Eriksen, Freij and W$ddot{a}$stlund, to give a unified generalization of these two identities. We provide for it a combinatorial proof by the functional digraph theory and another two algebraic proofs. Using the umbral representation of our generalized identity and the Abels binomial formula, we deduce several properties for $lambda$-factorials of $n$ and establish the curious relations between the generating functions of general and exponential types for any sequence of numbers or polynomials.
Recently, Deutsch and Elizalde studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in weighted set partitions. Let $A_{n,k}(mathbf{t})$ denote the total weight of partitions o
n $[n+1]$ with the largest singleton ${k+1}$. In this paper, explicit formulas for $A_{n,k}(mathbf{t})$ and many combinatorial identities involving $A_{n,k}(mathbf{t})$ are obtained by umbral operators and combinatorial methods. As applications, we investigate three special cases such as permutations, involutions and labeled forests. Particularly in the permutation case, we derive a surprising identity analogous to the Riordan identity related to tree enumerations, namely, begin{eqnarray*} sum_{k=0}^{n}binom{n}{k}D_{k+1}(n+1)^{n-k} &=& n^{n+1}, end{eqnarray*} where $D_{k}$ is the $k$-th derangement number or the number of permutations of ${1,2,dots, k}$ with no fixed points.
A {em Motzkin path} of length $n$ is a lattice path from $(0,0)$ to $(n,0)$ in the plane integer lattice $mathbb{Z}timesmathbb{Z}$ consisting of horizontal-steps $(1, 0)$, up-steps $(1,1)$, and down-steps $(1,-1)$, which never passes below the x-axis
. A {em $u$-segment {rm (resp.} $h$-segment {rm)}} of a Motzkin path is a maximum sequence of consecutive up-steps ({rm 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 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.
In this paper, the problem of pattern avoidance in generalized non-crossing trees is studied. The generating functions for generalized non-crossing trees avoiding patterns of length one and two are obtained. Lagrange inversion formula is used to obta
in the explicit formulas for some special cases. Bijection is also established between generalized non-crossing trees with special pattern avoidance and the little Schr{o}der paths.
In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
