190 Méthodes combinatoires, problèmes de dénombrement.

Méthodes combinatoires, problèmes de dénombrement.

algebra

Dénombrement

Principes de base

Définition 1. On dit qu’un ensemble $E$ est fini s’il est vide ou s’il existe $n \in N^{*}$ tel qu’il existe une bijection de $[[1, n]]$ dans $E$ . Dans ce cas, l’entier $n$ ne dépend pas de la bijection, on l’appelle cardinal de $E$ . Il est noté $∣ E ∣$ . Si $E$ est vide, on pose $∣ E ∣ = 0$ .

Proposition 2. Soient $E$ et $F$ deux ensembles.

Si $E$ est fini et s’il existe une injection de $E$ vers $F$ , alors $E$ est fini et $∣ E ∣ \leq ∣ F ∣$ .
Si $E$ est fini et s’il existe une surjection de $E$ vers $F$ , alors $F$ est fini et $∣ E ∣ \geq ∣ F ∣$ .
Si $E$ et s’il existe une bijection de $E$ vers $F$ , alors $F$ est fini et $∣ E ∣ = ∣ F ∣$ .

Corollaire 3. Soit $B$ un ensemble fini et $A \subseteq B$ . Alors $A$ est fini et $∣ A ∣ \leq ∣ B ∣$ . Si $∣ A ∣ = ∣ B ∣$ , alors $A = B$ .

Corollaire 4 (Principe des tiroirs). Soient $E$ et $F$ deux ensembles finis avec $∣ E ∣ > ∣ F ∣$ . Si $φ$ est une application de $E$ vers $F$ , alors il existe $y \in F$ ayant au moins deux antécédents par $φ$ dans $E$ .

Remarque 5 (Interprétation). Si on doit ranger $n + 1$ chaussettes dans $n$ tiroirs, alors un des tiroirs (au moins) contiendra deux chaussettes ou plus.

Proposition 6. Soient $A$ et $B$ deux ensembles finis. Alors,

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ .
$∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣$ .

Proposition 7 (Formule du crible de Poincaré). Soient $A_{1}, \dots, A_{n}$ des ensembles finis. Alors, $i = 1 ⋃ n A_{i} = k = 1 \sum n (- 1)^{k - 1} 1 \leq i_{1} < \dots < i_{k} \leq n \sum ∣ A_{i_{1}} \cap \dots \cap A_{i_{k}}$

[G-K]
p. 401

Exemple 8. Pour $n = 3$ , on a $∣ A_{1} \cap A_{2} \cap A_{3} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + ∣ A_{3} ∣ - ∣ A_{1} \cap A_{2} ∣ - ∣ A_{2} \cap A_{3} ∣ - - ∣ A_{1} \cap A_{3} ∣ + ∣ A_{1} \cup A_{2} \cup A_{3} ∣$

Lemme 9 (des bergers). Soient $A$ et $B$ deux ensembles. On suppose $A$ fini. Soit $φ : A \to B$ surjective telle que tout élément de $B$ admet exactement $a$ antécédents par $φ$ . Alors, $∣ A ∣ = \frac{∣ B ∣}{a}$

Combinatoire

Listes

[GOU21]
p. 301

Proposition 10. Soient $n$ ensembles finis $E_{1}, \dots, E_{n}$ . Le produit cartésien $E_{1} \times \dots \times E_{n}$ est un ensemble fini et vérifie $∣ E_{1} \times \dots \times E_{n} ∣ = ∣ E_{1} ∣ \times \dots \times ∣ E_{n} ∣$ . En particulier, pour un ensemble $E$ fini, on a $∣ E^{n} ∣ = ∣ E ∣^{n}$ .

Définition 11. Soit $E$ un ensemble et $p \in N^{*}$ . On appelle $p$ -liste (ou $p$ -uplet) de $E$ , tout élément $(x_{1}, \dots, x_{p})$ de $E^{p}$ .

Remarque 12.

Si $E$ est fini, il y a $∣ E ∣^{p}$ $p$ -listes de $E$ .
Dans une liste, l’ordre des éléments importe.

Exemple 13. Dans un jeu de $52$ cartes, le nombre de façons de tirer $10$ cartes avec remise est $5 2^{10}$ .

Arrangements

Définition 14. Soit $E$ un ensemble fini de cardinal $n$ . Soit $p$ un entier inférieur à $n$ . On appelle $p$ -arrangement de $E$ toute $p$ -liste de $E$ d’éléments distincts.

Proposition 15. En reprenant les notations précédentes, le nombre de $p$ -arrangements de $E$ est $A_{n}^{p} = n (n - 1) \dots (n - p + 1) = \frac{n !}{( n - p )!}$

Remarque 16.

Si $p = n$ , on trouve que le nombre de $n$ -arrangements est $n!$ .
Dans les arrangements, l’ordre des éléments importe, mais ceux-ci sont distincts.

Exemple 17. Dans un jeu de $52$ cartes, le nombre de façons de tirer $10$ cartes sans remise est $A_{52}^{10} = 52 \times \dots \times 43$ .

Application 18 (Nombre d’applications entre deux ensembles finis). Soient $E$ et $F$ deux ensembles finis.

L’ensemble des applications de $E$ vers $F$ , noté $F^{E}$ est fini, de cardinal $∣ F ∣^{∣ E ∣}$ .
Lorsque $∣ E ∣ \leq ∣ F ∣$ , l’ensemble des applications injectives de $E$ dans $F$ est fini, de cardinal $A_{n}^{p}$ .
L’ensemble des bijections de $E$ vers $E$ appelées permutations de $E$ , noté $S (E)$ , est fini et de cardinal $∣ E ∣!$ .

Corollaire 19. Soit $E$ un ensemble fini. Le nombre total de parties de $E$ est $∣ P (E) ∣ = 2^{∣ E ∣}$ .

Combinaisons

Définition 20. Soit $E$ un ensemble fini de cardinal $n$ . Soit $p \in N$ . On appelle $p$ -combinaison de $E$ toute partie de $E$ de cardinal $p$ . Ce nombre ne dépend que de $n$ et de $p$ , on le note $(p n)$ .

Proposition 21. Soient $n, p \in N$ . Alors, $(p n) = {\frac{n !}{p ! ( n - p )!} 0 si p \leq n sinon$

Remarque 22. Dans les combinaisons, l’ordre des éléments n’importe pas, mais ceux-ci sont distincts.

Exemple 23. Dans un jeu de $52$ cartes, le nombre de façons de tirer $10$ cartes simultanément est $(10 52)$ .

Définition 24. Soit $E$ un ensemble fini de cardinal $n$ . Soit $p$ un entier inférieur à $n$ . On appelle $p$ -combinaison avec répétition les $p$ -listes dans lesquelles ont autorise les répétions, mais dans lesquelles l’ordre ne compte pas.

Proposition 25. En reprenant les notations précédentes, il y a $(p n + p - 1)$ $p$ -combinaisons avec répétition.

Proposition 26. Soit $n \in N$ .

On a : $k = 0 \sum n (k n) = 2^{n}$
Soient $a$ et $b$ deux éléments d’une algèbre qui commutent. Alors, $(a + b)^{n} k = 0 \sum n (k n) a^{k} b^{n - k}$

p. 311

Application 27. Soit $(F_{n})$ la suite de Fibonacci définie par $F_{0} = 0$ , $F_{1} = 1$ et $\forall n \geq 2$ , $F_{n} = F_{n - 1} + F_{n - 2}$ . Alors, $\forall n \in N, F_{n} = \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}) = k = 0 \sum ⌊ \frac{n}{2} ⌋ (k n - k)$

En théorie des groupes

Soit $G$ un groupe fini.

Actions de groupes

[ULM21]
p. 71

Soit $X$ un ensemble fini. On considère une action $\cdot$ de $G$ sur $X$ .

Proposition 28. Soit $x \in X$ . Alors :

$∣ G \cdot x ∣ = (G : Stab_{G} (x))$ .
$∣ G ∣ = ∣ Stab_{G} (x) ∣∣ G \cdot x ∣$ .
$∣ G \cdot x ∣ = \frac{∣ G ∣}{∣ Stab _{G} ( x ) ∣}$

Théorème 29 (Formule des classes). Soit $Ω$ un système de représentants d’orbites de l’action de $G$ sur $X$ . Alors, $∣ X ∣ = ω \in Ω \sum ∣ G \cdot ω ∣ = ω \in Ω \sum (G : Stab_{G} (ω)) = ω \in Ω \sum \frac{∣ G ∣}{∣ Stab _{G} ( ω ) ∣}$

Définition 30. On définit :

$X^{G} = {x \in X ∣ \forall g \in G, g \cdot x = x}$ l’ensemble des points de $X$ laissés fixes par tous les éléments de $G$ .
$X^{g} = {x \in X ∣ g \cdot x = x}$ l’ensemble des points de $X$ laissés fixes par $g \in G$ .

Théorème 31 (Formule de Burnside). Le nombre $r$ d’orbites de $X$ sous l’action de $G$ est donné par $r = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣$

[I-P]
p. 121

Application 32. Deux colorations des faces d’un cube sont les mêmes si on peut passer de l’une à l’autre par une isométrie du dodécaèdre. Alors, le nombre de colorations distinctes d’un cube avec $c$ couleurs est $\frac{c ^{2}}{24} (c^{4} + 3^{2} + 12 c + 8)$

$p$ -groupes

[ROM21]
p. 22

Définition 33. On dit que $G$ est un $p$ -groupe s’il est d’ordre une puissance d’un nombre premier $p$ .

Proposition 34. Soit $p$ un nombre premier. Si $G$ est un $p$ -groupe opérant sur un ensemble $X$ , alors, $∣ X^{G} ∣ \equiv ∣ X ∣ mod p$ où $X^{G}$ désigne l’ensemble des points fixes de $X$ sous l’action de $G$ .

Corollaire 35. On note $G \cdot h_{1}, \dots, G \cdot h_{r}$ les classes de conjugaison de $G$ . Alors, $∣ G ∣ = ∣ Z (G) ∣ + i = 1 ∣ G \cdot h_{i} ∣ = 2 \sum r ∣ G \cdot h_{i} ∣ = ∣ Z (G) ∣ + i = 1 ∣ G \cdot h_{i} ∣ = 2 \sum r \frac{∣ G ∣}{∣ Stab _{G} ( h _{i} ) ∣}$

Corollaire 36. Soit $p$ un nombre premier. Le centre d’un $p$ -groupe non trivial est non trivial.

Corollaire 37. Soit $p$ un nombre premier. Un groupe d’ordre $p^{2}$ est toujours abélien.

Application 38 (Théorème de Cauchy). On suppose $G$ non trivial et fini. Soit $p$ un premier divisant l’ordre de $G$ . Alors il existe un élément d’ordre $p$ dans $G$ .

[GOU21]
p. 44

theoreme-de-sylow

Application 39 (Premier théorème de Sylow). On suppose $G$ fini d’ordre $n p^{α}$ avec $n, α \in N$ et $p$ premier tel que $p ∤ n$ . Alors, il existe un sous-groupe de $G$ d’ordre $p^{α}$ .

En théorie des corps finis

Soit $q = p^{n}$ avec $p$ premier et $n \geq 2$ .

Polynômes irréductibles

[GOZ]
p. 87

Théorème 40. $F_{q} = F_{p} [X] / (P)$ où $P \in F_{p} [X]$ est un polynôme irréductible de degré $n$ sur $F_{p}$ .

Corollaire 41.

Il existe des polynômes irréductibles de tout degré dans $F_{p} [X]$ .
Si $P \in F_{p} [X]$ est un polynôme irréductible sur $F_{p}$ de degré $n$ , alors $P$ divise $X^{q} - X$ . En particulier, il est scindé sur $F_{q}$ . Donc son corps de rupture $F_{q} = F_{p} [X] / (P)$ est aussi son corps de décomposition.

Théorème 42. Pour tout $j \in N^{*}$ , on note $I (p, q)$ l’ensemble des polynômes irréductibles unitaires de degré $j$ sur $F_{p}$ . Alors, $X^{q} - X = d ∣ n \prod Q \in I (p, q) \prod Q$

Corollaire 43. $q = d ∣ n \sum d ∣ I (p, d) ∣$

Définition 44. On définit la fonction de Möbius, notée $μ$ , par $μ : Z n \to \mapsto Z ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 si n = 1 si n = p_{1} \dots p_{k} avec p_{1}, \dots, p_{k} premiers distincts sinon$

Théorème 45 (Formule d’inversion de Möbius). Soient $f$ et $g$ des fonctions de $N^{*}$ dans $C$ telles que $\forall n \in N^{*}, f (n) = \sum_{d ∣ n} g (d)$ . Alors, $\forall n \in N^{*}, g (n) = d ∣ n \sum μ (d) f (\frac{n}{d})$

Corollaire 46. $\forall n \in N^{*}, ∣ I (p, q) ∣ = \frac{1}{n} d ∣ n \sum μ (d) p^{\frac{n}{d}} = \frac{1}{n} d ∣ n \sum μ (\frac{n}{d}) p^{d}$

Carrés dans les corps finis

p. 93

Proposition 47. On note $F_{q}^{2} = {x^{2} ∣ x \in F_{q}}$ et $F_{q}^{* 2} = F_{q}^{2} \cap F_{q}^{*}$ . Alors $F_{q}^{* 2}$ est un sous-groupe de $F_{q}^{*}$ .

Proposition 48.

Si $p = 2$ , $F_{q}^{2} = F_{q}$ , donc $F_{q}^{* 2} = F_{q}^{*}$ .
Si $p > 2$ , alors :
- $F_{q}^{* 2}$ est le noyau de l’endomorphisme de $F_{q}^{*}$ défini par $x \mapsto x^{\frac{q - 1}{2}}$ .
- $F_{q}^{* 2}$ est un sous-groupe d’indice $2$ de $F_{q}^{*}$ .
- $∣ F_{q}^{* 2} ∣ = \frac{q - 1}{2}$ et $∣ F_{q}^{2} ∣ = \frac{q + 1}{2}$ .
- $(- 1) \in F_{q}^{* 2} ⟺ q \equiv 1 mod 4$ .

Groupe linéaire sur un corps fini

[PER]
p. 119

Soit $V$ un espace vectoriel de dimension finie $n$ sur un corps $K$ .

Définition 49.

Le groupe linéaire de $V$ , $GL (V)$ est le groupe des applications linéaires de $V$ dans lui-même qui sont inversibles.
Le groupe spécial linéaire de $V$ , $SL (V)$ est le sous-groupe de $GL (V)$ constitué des applications de déterminant $1$ .
Les quotients de ces groupes par leur centre sont respectivement notés $PGL (V)$ et $PSL (V)$ .

p. 124

Proposition 50. On se place dans le cas où $K = F_{q}$ . Alors, les groupes précédents sont finis, et :

$∣ GL (V) ∣ = q^{\frac{n ( n - 1 )}{2}} ((q^{n} - 1) \dots (q - 1))$ .
$∣ PGL (V) ∣ = ∣ SL (V) ∣ = \frac{∣ GL ( V ) ∣}{q - 1}$ .
$∣ PSL (V) ∣ = ∣ SL (V) ∣ = \frac{∣ GL ( V ) ∣}{( q - 1 ) pgcd ( n , q - 1 )}$ .

En analyse

Probabilités sur un ensemble fini

[G-K]
p. 137

Soit $(Ω, A, P)$ un espace probabilisé.

Définition 51. Soit $E \subseteq Ω$ fini. On appelle loi uniforme sur $E$ la loi discrète définie sur $P (Ω)$ par $P (Ω) A \to \mapsto [[0, 1]] \frac{∣ A \cap E ∣}{∣ E ∣}$

Remarque 52. Il s’agit du nombre de cas favorables sur le nombre de cas possibles. Ainsi, $X$ suit la loi uniforme sur $E$ si on a $\forall x \in E, P (X = x) = \frac{1}{∣ E ∣}$ et $\forall x \in / E, P (X = x) = 0$ .

C’est, par exemple, la loi suivie par une variable aléatoire représentant le lancer d’un dé non truqué avec $E = [[1, 6]]$ .

Définition 53. Une variable aléatoire $X$ suit une loi de Bernoulli de paramètre $p \in [0, 1]$ , notée $B (p)$ , si $P (X = 1) = p$ et $P (X = 0) = 1 - p$ .

Proposition 54. En reprenant les notations précédentes, $X$ est une loi discrète et on a $P_{X} = (1 - p) δ_{0} + p δ_{1}$

Définition 55. Une variable aléatoire $X$ suit une loi de binomiale de paramètres $n \in N$ et $p \in [0, 1]$ , notée $B (n, p)$ , si $X$ est la somme de $n$ variables aléatoires indépendantes qui suivent des lois de Bernoulli de paramètre $p$ .

Proposition 56. En reprenant les notations précédentes, $X$ est une loi discrète et on a $\forall k \in N, P (X = k) = (k n) p^{k} (1 - p)^{n - k}$

Remarque 57. Il s’agit du nombre de succès pour $n$ tentatives.

C’est, par exemple, la loi suivie par une variable aléatoire représentant le nombre de Pile obtenus lors d’un lancer de pièce équilibrée.

Utilisation des séries pour dénombrer

[GOU21]
p. 312

Théorème 58 (Dérangements). Soit $n \in N^{*}$ . On note $D_{n}$ l’ensemble des permutations de $[[1, n]]$ sans point fixe. Alors, $∣ D_{n} ∣ = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !} = ⌊ \frac{n !}{e} + \frac{1}{2} ⌋$

Exemple 59. $n$ personnes laissent leur chapeau à un vestiaire. En repartant, chaque personne prend un chapeau au hasard. La probabilité que personne ne reprenne son propre chapeau est d’environ $\frac{1}{e}$ .

p. 314

nombres-de-bell

Théorème 60 (Nombres de Bell). Pour tout $n \in N^{*}$ , on note $B_{n}$ le nombre de partitions de $[[1, n]]$ . Par convention on pose $B_{0} = 1$ . Alors, $\forall k \in N^{*}, B_{k} = \frac{1}{e} n = 0 \sum + \infty \frac{n ^{k}}{n !}$