On a New Congruence in the Catalan Triangle

Abstract

For $0\le k\le n$, the number $C(n,k)$ represents the number of all lattice paths in the plane from the point $(0,0)$ to the point $(n,k)$, using steps $(1,0)$ and $(0,1)$, that never rise above the main diagonal $y=x$. The Fuss-Catalan number of order three $C_n^{(3)}$ represents the number of all lattice paths in the plane from the point $(0,0)$ to the point $(2n,n)$, using steps $(1,0)$ and $(0,1)$, that do not rise above the line $y=\frac{x}{2}$. We present a new alternating convolution formula for the numbers $C(2n,k)$. By using a new class of binomial sums that we call $M$ sums, we prove that this sum is divisible by $C_n^{(3)}$ and by the central binomial coefficient $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. We do this by examining the numbers $T(n,j)=\frac{1}{2n+1}\left(\genfrac{}{}{0ex}{}{2n+j}{j}\right)\left(\genfrac{}{}{0ex}{}{2n+1}{n+j+1}\right)$, for which we present a new combinatorial interpretation, connecting them to the generalized Schröder numbers of order two.

17 pages