Sommes classiques : énoncé (MPSI)
Sommes classiques
Pour $n\in\mathbb{N}$ : $$\sum_{k=0}^n\binom{n}{k}=2^n.$$ Preuve combinatoire : $\mathcal{P}(E)$ est la réunion disjointe des $\mathcal{P}_k(E)$ pour $0\le k\le n$.
Pour $n\ge1$, le binôme avec $a=-1$, $b=1$ donne $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$ : un ensemble non vide a autant de parties de cardinal pair que de cardinal impair, soit $2^{n-1}$ de chaque.
Chemins dans un quadrillage
On va de $(0,0)$ à $(p,q)$ par pas élémentaires $(1,0)$ (droite) ou $(0,1)$ (haut). Un chemin compte $p+q$ pas, dont $p$ vers la droite. Il est déterminé par l'ensemble des numéros des pas vers la droite, partie à $p$ éléments de $\llbracket1,p+q\rrbracket$. Il y a donc $\binom{p+q}{p}$ chemins.
Pour $(3,2)$ : $\binom{5}{3}=10$ chemins.
Autre exemple : un polygone convexe à $n$ sommets a $\binom{n}{2}-n=\frac{n(n-3)}{2}$ diagonales (segments joignant deux sommets, moins les $n$ côtés). Pour $n=10$ : $45-10=35$.