Exercice 10, § 5

Soit $q_{n,k}$ le nombre des applications strictement croissantes u de $\{1, k\}$ dans $\{1, n\}$ telles que, pour tout x pair (resp. impair), u(x) soit pair (resp. impair). Montrer que l’on a q_{n,k} = q_{n-1,k-1} + q_{n-2,k}. En déduire la formule

où $\left[ \frac{n+k}{2} \right]$ est la partie entière du quotient de $n + k$ par 2.