Some more properties of Catalan numbers (Q1193445)

The Catalan numbers \(C(n)\) are introduced as the numbers of ways of bracketing a non-associative non-commutative product \(x_ 0x_ 1\dots x_ n\) of \(n+1\) terms. Thus \(C(0)=C(1)=1\), \(C(2)=2\) \([(x_ 0x_ 1)x_ 2\), \(x_ 0(x_ 1x_ 2)]\). As is well known [\textit{M. Aigner}, Combinatorial Theory (1979; Zbl 0415.05001), p. 85] \(C(n)\) is given by \[ C(n)={1\over n+1}{2n\choose n}.\tag{1} \] The authors follow the interpretation of Catalan numbers \(C(n)\) as number of (non-strictly) increasing monoton functions \(f:[1,n]\to[1,n]\) with \(f(n)=n\). These functions can be seen as under-diagonal walks (only rightward \(r\) and upward \(u\) steps) of length \(2n\) in the integer lattice \([0,n]\times[0,n]\) (terminating in \((n,n))\), by which they arrive at formula (1). The authors show another interpretation of these walks as words of length \(2n\) of the Dyck language on the alphabet \(\{r,u\}\). Their induction proceeds by showing with the method of generating functions that \[ nC(n)=\sum^{n-1}_{j=0}C(j){2(n-j)-1\choose n-j}. \] This is generalized to \(n\)-walks (rightward, leftward, upward, downward) in the integer lattice of above beginning with (0,0) and ending on the \(y\)-axis. A bijection is shown between these walks and \((n+1)\)-node binary trees. Therefore, if \(C'(n)\) is the number of these walks, \(C'(n)=C(n+1)\), by the usual identification of bracketing and binary trees. But the authors can enumerate \(C'(n)\) in another way (introducing a new formal language on the alphabet \(\{r,l,u,d\})\) to give a simple proof of Touchard's formula \[ C(n+1)=\sum^{[n/2]}_{k=0}2^{n-2k}{n\choose 2k}C(k). \]