Encadrements de coefficients binomiaux et trinomiaux

(i) Coefficients binomiaux. Montrons $\binom nk\,k!\,(n - k)! = n!$ pour $k \leqslant n$, par récurrence sur $n$. Pour $k = 0$, c'est $\binom n0 = 1$. Pour $k + 1 \leqslant n + 1$, la relation $(k + 1)\binom{n+1}{k+1} = (n + 1)\binom nk$ (Binôme de Newton, (i)) et l'hypothèse de récurrence donnent $$\begin{aligned} &\binom{n+1}{k+1}(k + 1)!\,(n - k)! \\ &= (n + 1)\binom nk\,k!\,(n - k)! = (n + 1)!. \end{aligned}$$

Mots. Récurrence sur $r$ ; pour $r = 1$, il y a un seul mot, et $m!/m! = 1$. Pour $r \geqslant 2$, un mot est déterminé par l'ensemble des $m_r$ positions de la lettre $r$, partie à $m_r$ éléments de $\{1, \dots, m\}$, et par le mot sur $\{1, \dots, r - 1\}$ lu sur les autres positions. Il y a $\binom m{m_r}$ telles parties (Binôme de Newton, (v)), d'où le nombre $$\frac{m!}{m_r!\,(m - m_r)!}\cdot\frac{(m - m_r)!}{m_1!\cdots m_{r-1}!}.$$

Enfin les $3^n$ mots de longueur $n$ sur trois lettres se répartissent selon leurs nombres $(i, j, k)$ de chaque lettre, d'où $\sum n!/(i!j!k!) = 3^n$.

(ii) On a $c_1 = \frac12$ et $$\frac{c_{n+1}}{c_n} = \frac{(2n + 1)(2n + 2)}{4(n + 1)^2} = \frac{2n + 1}{2n + 2}.$$ Posons $u_n = (2n + 1)c_n^2$ et $v_n = 4n\,c_n^2$. Alors $$\begin{aligned} \frac{u_{n+1}}{u_n} &= \frac{(2n + 1)(2n + 3)}{(2n + 2)^2} < 1, \\ \frac{v_{n+1}}{v_n} &= \frac{(2n + 1)^2}{4n(n + 1)} > 1, \end{aligned}$$ puisque $(2n + 1)(2n + 3) = (2n + 2)^2 - 1$ et $(2n + 1)^2 = 4n(n + 1) + 1$. Comme $u_0 = 1$ et $v_1 = 1$, on a $u_n \leqslant 1 \leqslant v_n$ pour $n \geqslant 1$.

(iii) Comptons les parties à $n$ éléments de $\{1, \dots, 2n\}$ selon le nombre $i$ de leurs éléments dans $\{1, \dots, n\}$ : une telle partie est la réunion d'une partie à $i$ éléments de $\{1, \dots, n\}$ et d'une partie à $n - i$ éléments de $\{n + 1, \dots, 2n\}$. Il y en a $\binom ni\binom n{n-i} = \binom ni^2$, par la formule de (i), et au total $\binom{2n}n$.

(iv) Décroissance. En convenant que $t_n$ est nul si un indice est négatif, on vérifie, en réduisant au même dénominateur, que $$\begin{aligned} &t_{n+1}(i, j, k) \\ &= \tfrac13\big(t_n(i - 1, j, k) + t_n(i, j - 1, k) \\ &\qquad + t_n(i, j, k - 1)\big), \end{aligned}$$ le second membre valant $\frac{n!}{i!j!k!3^{n+1}}(i + j + k)$ ; c'est une moyenne de trois nombres au plus égaux à $M_n$.

Le maximum. Si $i \geqslant j + 2$, alors $$\frac{t_n(i - 1, j + 1, k)}{t_n(i, j, k)} = \frac{i}{j + 1} > 1 ;$$ un triplet où le maximum est atteint, sur l'ensemble fini des triplets, a donc ses coordonnées deux à deux distantes d'au plus $1$, de la forme $a$ ou $a + 1$. Pour $n = 3m$, leur somme $3m = 3a + s$, où $s \in \{0, 1, 2\}$ est le nombre de coordonnées égales à $a + 1$, impose $s = 0$ et $a = m$.

La majoration. Soit $b_m = m\,t_{3m}(m, m, m)$. On a $b_1 = \frac{3!}{27} = \frac29$ et $$\frac{b_{m+1}}{b_m} = \frac{(3m + 1)(3m + 2)}{9m(m + 1)} = 1 + x_m,$$ avec $x_m = \frac{2}{9m(m + 1)} \in [0, 1[$. Comme $1 + x \leqslant \frac1{1 - x}$, puisque $(1 + x)(1 - x) \leqslant 1$, et que $\prod_j(1 - x_j) \geqslant 1 - \sum_j x_j$ par récurrence, on obtient $$\begin{aligned} b_m &= b_1\prod_{j < m}(1 + x_j) \leqslant \frac{b_1}{\prod_{j < m}(1 - x_j)} \\ &\leqslant \frac{b_1}{1 - \sum_{j \geqslant 1} x_j} = \frac{2/9}{1 - 2/9} = \frac27, \end{aligned}$$ la somme $\sum_{j \geqslant 1} x_j = \frac29\sum_j\big(\frac1j - \frac1{j + 1}\big) = \frac29$ étant télescopique.

Enfin, pour $n \geqslant 3$, soit $m \geqslant 1$ le quotient de $n$ par $3$ : $3m \geqslant n - 2 \geqslant \frac n3$, et par la décroissance, $M_n \leqslant M_{3m} \leqslant \frac2{7m} \leqslant \frac{18}{7n}$.