On considère une grille rectangulaire dont les sommets ont des coordonnées entières. Une fourmi part du point $A(0;0)$ et veut atteindre le point $B(6;4)$. À chaque étape, elle se déplace soit d'un pas vers la droite ($+1$ en abscisse), soit d'un pas vers le haut ($+1$ en ordonnée). Tous les chemins sont donc « monotones » et de longueur minimale.

1. Justifier que tout chemin de $A$ à $B$ comporte exactement $10$ pas, puis montrer que le nombre total de chemins de $A$ à $B$ est $\left(\genfrac{}{}{0ex}{}{10}{4}\right)$. Calculer ce nombre.

2. On note $C(2;3)$. Combien de chemins de $A$ à $B$ passent par le point $C$ ?

3. En distinguant, parmi tous les chemins de $A$ à $B$, le tout dernier pas (celui qui arrive en $B$), retrouver la relation de Pascal $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$$ dans le cas $n=9$, $k=3$. Énoncer le principe général.

4. Démontrer la relation de Pascal $\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ par le calcul, pour $0\le k\le n-1$.

On appelle mot binaire de longueur $n$ toute suite ordonnée de $n$ symboles, chacun valant $0$ ou $1$ (par exemple $0110$ est un mot binaire de longueur $4$). On travaille ici avec $n=8$.

1. Combien existe-t-il de mots binaires de longueur $8$ ? Combien d'entre eux contiennent exactement $k$ symboles égaux à $1$ (pour un entier $k$ fixé, $0\le k\le 8$) ?

2. En classant les mots binaires de longueur $8$ selon leur nombre de $1$, démontrer que $$\sum _{k=0}^8\left(\genfrac{}{}{0ex}{}{8}{k}\right)=2^8.$$ Généraliser la relation à un entier $n$ quelconque et indiquer le lien avec le nombre de parties d'un ensemble à $n$ éléments.

3. Démontrer que pour tout entier $n\ge 1$, $$\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0.$$ (On pourra utiliser la formule du binôme de Newton.)

4. En déduire que dans un ensemble à $n\ge 1$ éléments, il y a autant de parties de cardinal pair que de parties de cardinal impair, et donner leur nombre commun.