Combinatoire et dénombrement

Le tableau consiste à répartir les 8 joueurs en 4 paires ordonnées par position dans le tableau. On choisit l'ordre des 8 joueurs : $8!$ permutations. Mais au sein de chaque match, l'ordre des 2 joueurs n'importe pas ($2^4$ symétries), et l'ordre des matchs au sein d'une même moitié de tableau non plus. Plus simplement : on choisit 2 joueurs parmi 8 pour le match 1 : $\binom{8}{2}$, puis 2 parmi 6 pour le match 2 : $\binom{6}{2}$, etc. $\binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2} = 28 \times 15 \times 6 \times 1 = \dfrac{8!}{2^4} = 2\,520$ Si l'ordre des matchs dans le tableau compte (positions fixes) : $\boxed{2\,520}$

À chaque match, un des 2 joueurs gagne. Il y a $4 + 2 + 1 = 7$ matchs au total. Pour un tableau fixé, le nombre de parcours est : $2^7 = \boxed{128}$

- Choix du vainqueur : 8 - Choix du finaliste (battu en finale) : 7 - Choix des 2 demi-finalistes (battus en demi) : $\binom{6}{2} = 15$ $8 \times 7 \times 15 = \boxed{840}$

Le joueur 1 gagne tous ses matchs et remporte le tournoi. Le joueur 2 n'est pas nécessairement finaliste : si les joueurs 1 et 2 sont dans la **même moitié de tableau**, ils se rencontrent en demi-finale, et le joueur 2 est éliminé avant la finale. Par exemple, avec le tableau [1 vs 2, 3 vs 4 | 5 vs 6, 7 vs 8] : le joueur 1 bat 2 en quart, puis bat 3 ou 4 en demi, et affronte le vainqueur de l'autre moitié en finale. Le joueur 2 est éliminé dès le premier tour. Le finaliste serait le meilleur joueur de **l'autre moitié** du tableau.

Considérons un ensemble $E$ de $m+n$ éléments, partitionné en un groupe $A$ de $m$ éléments et un groupe $B$ de $n$ éléments. Le membre de gauche $\binom{m+n}{p}$ compte les parties de $E$ à $p$ éléments. Pour former une telle partie, on choisit $k$ éléments dans $A$ et $p-k$ éléments dans $B$ (avec $0 \leq k \leq p$). Le nombre de choix est $\binom{m}{k}\binom{n}{p-k}$. En sommant sur toutes les valeurs possibles de $k$, on obtient le membre de droite. Cette partition en cas disjoints prouve l'identité. $\square$

En appliquant Vandermonde avec $m = n$ et $p = n$ : $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}$ Or $\binom{n}{n-k} = \binom{n}{k}$ par symétrie. Donc : $\boxed{\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}}$

D'après la formule précédente avec $n = 5$ : $\sum_{k=0}^{5} \binom{5}{k}^2 = \binom{10}{5} = 252$ **Vérification :** $1 + 25 + 100 + 100 + 25 + 1 = \boxed{252}$ ✓.

Membre de gauche : $\binom{7}{3} = 35$. Membre de droite : $\binom{3}{0}\binom{4}{3} + \binom{3}{1}\binom{4}{2} + \binom{3}{2}\binom{4}{1} + \binom{3}{3}\binom{4}{0}$ $= 1 \times 4 + 3 \times 6 + 3 \times 4 + 1 \times 1 = 4 + 18 + 12 + 1 = 35 \quad ✓$

On choisit 4 élèves parmi 12 pour G1, puis 4 parmi 8 pour G2, puis les 4 restants forment G3 : $\binom{12}{4} \times \binom{8}{4} \times \binom{4}{4} = 495 \times 70 \times 1 = \boxed{34\,650}$ On reconnaît le coefficient multinomial $\dfrac{12!}{4! \times 4! \times 4!} = 34\,650$.

Si les groupes sont identiques, chaque répartition a été comptée $3! = 6$ fois (une pour chaque permutation des 3 groupes) dans le calcul précédent. $\dfrac{34\,650}{3!} = \dfrac{34\,650}{6} = \boxed{5\,775}$

On choisit 3 élèves parmi 12 pour le groupe de 3, puis 4 parmi 9 pour le groupe de 4, puis les 5 restants : $\binom{12}{3} \times \binom{9}{4} \times \binom{5}{5} = 220 \times 126 \times 1 = \boxed{27\,720}$

Groupes numérotés : $\binom{12}{3} \times \binom{9}{3} \times \binom{6}{6} = 220 \times 84 \times 1 = 18\,480$. Les deux groupes de 3 sont indistinguables, donc on divise par $2!$ : $\dfrac{18\,480}{2} = \boxed{9\,240}$ (On ne divise que par $2!$ et non $3!$ car seuls les deux groupes de même taille sont interchangeables.)

D'après la formule du binôme de Newton : $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k = \binom{n}{0} + \binom{n}{1}x + \binom{n}{2}x^2 + \cdots + \binom{n}{n}x^n$

$(1+(-1))^n = 0^n = 0$ pour $n \geq 1$. Or $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$. Avec $x = -1$ : $0 = \sum_{k=0}^{n} \binom{n}{k}(-1)^k$ $\boxed{\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0}$ Ce qui s'écrit aussi : $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots + (-1)^n\binom{n}{n} = 0$.

D'après la question 2 : $\sum_{k \text{ pair}} \binom{n}{k} - \sum_{k \text{ impair}} \binom{n}{k} = 0$. Donc $\sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k}$. Or leur somme vaut $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. Donc chacune vaut $\dfrac{2^n}{2} = \boxed{2^{n-1}}$.

$(1+2)^n = 3^n$. Or $(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$. Avec $x = 2$ : $\boxed{\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n}$ Application numérique pour $n = 5$ : $\binom{5}{0} + 2\binom{5}{1} + 4\binom{5}{2} + 8\binom{5}{3} + 16\binom{5}{4} + 32\binom{5}{5} = 1 + 10 + 40 + 80 + 80 + 32 = 243 = 3^5$ ✓.

D'après la question précédente avec $x = 3$ et $n = 6$ : $\sum_{k=0}^{6} 3^k \binom{6}{k} = (1+3)^6 = 4^6 = \boxed{4\,096}$

Chaque chemin est composé de $n$ pas à droite (D) et $n$ pas en haut (H), soit $2n$ pas au total. Le nombre de chemins est : $\binom{2n}{n}$

$\binom{8}{4} = \dfrac{8 \times 7 \times 6 \times 5}{4!} = \dfrac{1680}{24} = \boxed{70}$

Un tel chemin se décompose en : - Un chemin de $(0,0)$ à $(2,2)$ : $\binom{4}{2} = 6$ - Un chemin de $(2,2)$ à $(4,4)$ : $\binom{4}{2} = 6$ Par le principe multiplicatif : $6 \times 6 = \boxed{36}$

Le chemin se décompose en 3 étapes : - $(0,0) \to (1,2)$ : $\binom{3}{2} = 3$ (3 pas : 1D + 2H) - $(1,2) \to (3,3)$ : $\binom{3}{1} = 3$ (3 pas : 2D + 1H) - $(3,3) \to (4,4)$ : $\binom{2}{1} = 2$ (2 pas : 1D + 1H) Total : $3 \times 3 \times 2 = \boxed{18}$

C'est le nombre de combinaisons de 6 parmi 49 : $\binom{49}{6} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!} = \dfrac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{720} = \boxed{13\,983\,816}$

On choisit 3 bons numéros parmi 6, et 3 mauvais parmi les $49 - 6 = 43$ restants : $\binom{6}{3} \times \binom{43}{3} = 20 \times 12\,341 = \boxed{246\,820}$ Où $\binom{43}{3} = \dfrac{43 \times 42 \times 41}{6} = 12\,341$.

Il n'y a qu'une seule grille gagnante : $P = \dfrac{1}{\binom{49}{6}} = \dfrac{1}{13\,983\,816} \approx \boxed{7{,}15 \times 10^{-8}}$ Soit environ 1 chance sur 14 millions.

On additionne les cas 4, 5 et 6 bons numéros : **4 bons :** $\binom{6}{4}\binom{43}{2} = 15 \times 903 = 13\,545$ **5 bons :** $\binom{6}{5}\binom{43}{1} = 6 \times 43 = 258$ **6 bons :** $\binom{6}{6}\binom{43}{0} = 1$ $P = \dfrac{13\,545 + 258 + 1}{13\,983\,816} = \dfrac{13\,804}{13\,983\,816} \approx \boxed{9{,}87 \times 10^{-4}}$ Soit environ 1 chance sur 1\,013.

Si 1 est dans le sous-ensemble, on choisit librement les 9 autres éléments (chacun est pris ou non) : $2^9 = \boxed{512}$

Les éléments 1 et 2 sont imposés, 3 est exclu. Les 7 éléments restants (4 à 10) sont libres : $2^7 = \boxed{128}$

Les nombres pairs de $E$ sont $\{2, 4, 6, 8, 10\}$ (5 éléments) et les impairs sont $\{1, 3, 5, 7, 9\}$ (5 éléments). Par le complémentaire : sous-ensembles à 4 éléments **sans aucun pair** (4 impairs parmi 5) : $\binom{5}{4} = 5$ Sous-ensembles à 4 éléments avec au moins un pair : $\binom{10}{4} - 5 = 210 - 5 = \boxed{205}$

La somme est paire si et seulement si le nombre d'éléments impairs est pair (0, 2 ou 4). Les éléments impairs de $E$ : $\{1,3,5,7,9\}$ (5 éléments). Les pairs : $\{2,4,6,8,10\}$ (5 éléments). **0 impairs, 5 pairs :** $\binom{5}{0}\binom{5}{5} = 1$ **2 impairs, 3 pairs :** $\binom{5}{2}\binom{5}{3} = 10 \times 10 = 100$ **4 impairs, 1 pair :** $\binom{5}{4}\binom{5}{1} = 5 \times 5 = 25$ Total : $1 + 100 + 25 = \boxed{126}$ **Remarque :** $126 = \dfrac{252}{2} = \dfrac{\binom{10}{5}}{2}$. Par symétrie, la moitié des sous-ensembles à 5 éléments ont une somme paire.

$(1+x)^n(1-x)^n = [(1+x)(1-x)]^n = (1-x^2)^n$

En posant $y = x^2$ dans $(1-y)^n$ : $(1-x^2)^n = \sum_{p=0}^{n} \binom{n}{p}(-1)^p x^{2p}$ Le coefficient de $x^{2p}$ est $(-1)^p \binom{n}{p}$, et les termes de degré impair sont nuls.

Le coefficient de $x^{2p}$ dans $(1+x)^n$ est $\binom{n}{j}$ pour $x^j$, et dans $(1-x)^n$ est $(-1)^k\binom{n}{k}$ pour $x^k$. Le coefficient de $x^{2p}$ dans le produit est : $\sum_{k=0}^{2p} \binom{n}{k}(-1)^k \binom{n}{2p-k}$ En identifiant avec le résultat de la question 2 : $\boxed{\sum_{k=0}^{2p} (-1)^k \binom{n}{k}\binom{n}{2p-k} = (-1)^p \binom{n}{p}}$

Pour $p = 0$ : le coefficient de $x^0$ est : $\sum_{k=0}^{0} (-1)^0 \binom{n}{0}\binom{n}{0} = 1$ Et $(-1)^0 \binom{n}{0} = 1$. ✓ Pour $p = 1$ (plus intéressant) : $\binom{n}{0}\binom{n}{2} - \binom{n}{1}^2 + \binom{n}{2}\binom{n}{0} = -\binom{n}{1}$ $2\binom{n}{2} - n^2 = -n \implies n(n-1) - n^2 = -n \implies -n = -n \quad ✓$

C'est un arrangement de 4 parmi 10 : $A_{10}^4 = 10 \times 9 \times 8 \times 7 = \boxed{5\,040}$

Un tirage ordonné croissant correspond à un **unique** sous-ensemble de 4 jetons (l'ordre est imposé). Il y a autant de tirages ordonnés croissants que de combinaisons de 4 parmi 10 : $\binom{10}{4} = 210$ **Autrement dit :** sur les $4! = 24$ ordres possibles d'un même sous-ensemble, un seul est croissant. $\dfrac{5\,040}{24} = \boxed{210}$

Nombres pairs dans $\{1, \ldots, 10\}$ : $\{2, 4, 6, 8, 10\}$, soit 5. Nombres impairs : $\{1, 3, 5, 7, 9\}$, soit 5. $\binom{5}{2} \times \binom{5}{2} = 10 \times 10 = \boxed{100}$

La somme de 4 nombres est paire si et seulement si le nombre d'impairs est pair (0, 2 ou 4). **0 impairs :** $\binom{5}{0}\binom{5}{4} = 1 \times 5 = 5$ **2 impairs :** $\binom{5}{2}\binom{5}{2} = 10 \times 10 = 100$ **4 impairs :** $\binom{5}{4}\binom{5}{0} = 5 \times 1 = 5$ $5 + 100 + 5 = \boxed{110}$ **Vérification :** Total = $\binom{10}{4} = 210$. Somme impaire : $210 - 110 = 100$. Les cas « somme paire » et « somme impaire » ne sont pas symétriques car les 4 éléments sont tirés sans remise.

Chaque corde relie 2 points distincts. Le nombre de cordes est : $\binom{n}{2} = \dfrac{n(n-1)}{2}$

Pour $n = 6$ : $\binom{6}{2} = \dfrac{6 \times 5}{2} = \boxed{15}$ cordes. Pour $n = 10$ : $\binom{10}{2} = \dfrac{10 \times 9}{2} = \boxed{45}$ cordes.

Deux cordes se coupent à l'intérieur du cercle si et seulement si leurs 4 extrémités sont distinctes. En effet, 4 points sur un cercle déterminent exactement un point d'intersection intérieur (celui des 2 « diagonales » du quadrilatère convexe). Le nombre de points d'intersection intérieurs est donc le nombre de façons de choisir 4 points parmi $n$ : $\binom{n}{4}$

$\binom{6}{4} = \binom{6}{2} = \boxed{15}$ Avec 6 points sur un cercle et la condition de position générale, on obtient 15 cordes et 15 points d'intersection intérieurs.