Somme des carrés : énoncé (MPSI)
Somme des carrés
Avec $p=q=n$ dans Vandermonde et la symétrie $\binom{n}{n-k}=\binom{n}{k}$ : $$\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}.$$ Contrôle : $n=3$ donne $1+9+9+1=20=\binom{6}{3}$.
Partage selon le plus grand élément
Montrons que, pour $0\le k\le n$ : $\sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$.
On compte les parties à $k+1$ éléments de $\llbracket1,n+1\rrbracket$ selon leur plus grand élément $m$. On a $m\in\llbracket k+1,n+1\rrbracket$, et les $k$ autres éléments forment une partie quelconque à $k$ éléments de $\llbracket1,m-1\rrbracket$ : $\binom{m-1}{k}$ choix. Avec $j=m-1\in\llbracket k,n\rrbracket$, le principe additif donne la formule.
Contrôle : $k=1$, $n=4$ donne $1+2+3+4=10=\binom{5}{2}$.
Anagrammes
Combien de mots (suites de lettres) s'écrivent avec les lettres de ANANAS ? Il y a $6$ positions, avec $3$ A, $2$ N et $1$ S.
Par choix successifs : on choisit les positions des A ($\binom{6}{3}=20$), puis celles des N parmi les $3$ restantes ($\binom{3}{2}=3$), le S occupe la dernière : $20\times3=60$.
Par le lemme des bergers : les $6!=720$ ordonnements de six jetons distincts $A_1,A_2,A_3,N_1,N_2,S$ donnent chaque mot exactement $3!\times2!=12$ fois (permutations des A entre eux et des N entre eux). D'où $720/12=60$.
Solutions entières d'une équation
Combien de triplets $(x_1,x_2,x_3)\in\mathbb{N}^3$ vérifient $x_1+x_2+x_3=4$ ?
On associe à un triplet le mot formé de $x_1$ étoiles, une barre, $x_2$ étoiles, une barre, $x_3$ étoiles. Par exemple $(1,0,3)\mapsto\star|\,|\star\star\star$. C'est une bijection vers les mots de longueur $6$ contenant $4$ étoiles et $2$ barres, déterminés par la position des barres : $\binom{6}{2}=15$ solutions.
Plus généralement, le nombre de solutions de $x_1+\cdots+x_k=n$ dans $\mathbb{N}^k$ vaut $\binom{n+k-1}{k-1}$. Ce résultat n'est pas au programme : il se redémontre par cette bijection.