Question 50
For integer $n, m \geq 1$, let $A(n, m)$ denote the number of functions $f:\{1,2, \ldots, n\} \rightarrow \{1,2, \ldots, m\}$ such that $f(j)-f(i) \leq j-i$ for all $1 \leq i \lt j \leq n$, and let $B(n, m)$ denote the number of functions $g:\{0,1, \ldots, 2n+m\} \rightarrow \{0,1, \ldots, m\}$ such that $g(0)=0$, $g(2n+m)=m$, and $|g(i)-g(i-1)|=1$ for all $1 \leq i \leq 2n+m$. Prove that $A(n, m) = B(n, m)$.