Fil directeur¶
Identifier d'abord la structure combinatoire d'un problème avant de compter : décomposer les cas, construire des bijections, utiliser les coefficients binomiaux, l'inclusion-exclusion, le double comptage ou une action de groupe lorsque la situation l'exige.
Positionnement¶
| Code | Sujet | Lien avec 310 |
|---|---|---|
| 102 | Permutations d'un ensemble fini, groupe symétrique. Applications. | Comptage de permutations, cycles, signatures |
| 133 | Groupe opérant sur un ensemble. Exemples et applications. | Orbites, stabilisateurs, dénombrement par symétries |
| 310 | Exercices faisant intervenir des dénombrements. | Sujet central de ce Labo |
Le fil directeur est :
$$ \boxed{ \text{structure combinatoire} \rightarrow \text{méthode de comptage} \rightarrow \text{preuve} } $$
Exercices progressifs¶
Exercice 1 — Double comptage et identité de Pascal¶
Montrer combinatoirement que
$$ \binom nk+\binom n{k+1} = \binom{n+1}{k+1}. $$
Exercice 2 — Principe d'inclusion-exclusion¶
Déterminer le nombre d'entiers de $\{1,\ldots,1000\}$ divisibles par au moins l'un des entiers $2$, $3$ ou $5$.
On pourra introduire les ensembles
$A_2$, $A_3$ et $A_5$
des multiples respectifs de $2$, $3$ et $5$.
Exercice 3 — Permutations avec répétitions¶
Combien d'anagrammes distinctes peut-on former avec les lettres du mot
MISSISSIPPI ?
Écrire le résultat sous forme factorielle avant toute simplification.
Exercice 4 — Principe des tiroirs¶
Soient $n+1$ entiers distincts choisis dans
$\{1,2,\ldots,2n\}$.
Montrer qu'il existe deux nombres parmi eux tels que l'un divise l'autre.
Exercice 5 — Action de groupe et lemme de Burnside¶
On colorie les quatre sommets d'un carré avec trois couleurs.
Deux coloriages sont considérés comme identiques lorsqu'ils se déduisent l'un de l'autre par une rotation du carré.
Déterminer le nombre de coloriages distincts.
On pourra faire agir le groupe des rotations du carré sur l'ensemble des coloriages et utiliser le lemme de Burnside.
Exercice 2 — Dérangements et inclusion-exclusion¶
On appelle dérangement une permutation de $\{1,\ldots,n\}$ sans point fixe.
Montrer que le nombre $D_n$ de dérangements vaut
$$ D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. $$
Motivation¶
Relier dénombrement, permutations et inclusion-exclusion.
Corrigé
Posons
$$ A_i = \{\sigma\in S_n:\sigma(i)=i\}. $$
Les dérangements sont les permutations n'appartenant à aucun $A_i$.
Par inclusion-exclusion,
$$ D_n = n! - \sum_i |A_i| + \sum_{i<j}|A_i\cap A_j| -\cdots. $$
Si $k$ points sont imposés fixes, les $n-k$ autres peuvent être permutés librement :
$$ |A_{i_1}\cap\cdots\cap A_{i_k}| = (n-k)!. $$
Il y a
$$ \binom nk $$
choix pour les $k$ points fixes.
Ainsi
$$ D_n = \sum_{k=0}^{n} (-1)^k \binom nk (n-k)!. $$
Or
$$ \binom nk(n-k)! = \frac{n!}{k!}. $$
Donc
$$ \boxed{ D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} }. $$
Exercice 3 — Permutations de type cyclique¶
Combien y a-t-il de permutations de $S_7$ ayant exactement :
- deux cycles de longueur $2$ ;
- un cycle de longueur $3$ ?
Motivation¶
Faire le pont avec la leçon 102 — groupe symétrique.
Corrigé
Le type cyclique est
$$ 2^2\,3^1. $$
La formule générale donne
$$ \frac{7!} {2^2\,2!\,3}. $$
Ainsi
$$ \frac{5040}{4\times2\times3} = 210. $$
Donc il existe
$$ \boxed{210} $$
permutations de ce type.
Justification des facteurs¶
- division par $2$ pour les rotations internes de chaque 2-cycle ;
- division par $3$ pour les rotations du 3-cycle ;
- division par $2!$ car les deux cycles de longueur 2 sont indiscernables.
Exercice 4 — Colorier un carré à symétrie près¶
On colorie les quatre sommets d'un carré avec deux couleurs : noir et blanc.
Deux coloriages sont considérés identiques s'ils se déduisent l'un de l'autre par une rotation du carré.
Combien existe-t-il de coloriages distincts ?
Motivation¶
Introduire la formule de Burnside et faire le pont avec 133 — groupe opérant.
Corrigé
Le groupe des rotations du carré est
$$ C_4 = \{e,r,r^2,r^3\}. $$
L'ensemble de tous les coloriages possède
$$ 2^4=16 $$
éléments.
Identité¶
Tous les 16 coloriages sont fixes :
$$ |\operatorname{Fix}(e)|=16. $$
Rotation de $180^\circ$¶
Les sommets opposés doivent avoir la même couleur.
On a donc deux choix indépendants :
$$ |\operatorname{Fix}(r^2)|=2^2=4. $$
Rotations de $90^\circ$ et $270^\circ$¶
Tous les sommets doivent avoir la même couleur :
$$ |\operatorname{Fix}(r)| = |\operatorname{Fix}(r^3)| = 2. $$
Par Burnside,
$$ |X/C_4| = \frac14(16+4+2+2) = 6. $$
Donc
$$ \boxed{6} $$
coloriages distincts à rotation près.
Exercice 5 — Dénombrement et probabilités¶
On tire simultanément $5$ cartes dans un jeu de $52$ cartes.
Calculer la probabilité d'obtenir exactement deux as.
Motivation¶
Montrer comment un problème probabiliste fini se ramène à un quotient de dénombrements.
Corrigé
Le nombre total de mains de cinq cartes est
$$ \binom{52}{5}. $$
Pour avoir exactement deux as :
- choisir $2$ as parmi $4$ ;
- choisir $3$ cartes non-as parmi $48$.
Le nombre de mains favorables vaut
$$ \binom42\binom{48}{3}. $$
Ainsi
$$ \boxed{ \mathbb P = \frac{ \binom42\binom{48}{3} }{ \binom{52}{5} } }. $$
Exercice phare¶
Pourquoi ce développement ?¶
Il relie directement :
- groupes finis ;
- actions de groupes ;
- orbites ;
- stabilisateurs ;
- dénombrement ;
- symétries.
Il crée donc un pont fort entre 133 et 310.
Énoncé¶
Soit un groupe fini $G$ agissant sur un ensemble fini $X$.
Alors le nombre d'orbites est
$$ \boxed{ |X/G| = \frac1{|G|} \sum_{g\in G} |\operatorname{Fix}(g)| }. $$
Idée de preuve¶
On considère l'ensemble
$$ E = \{(g,x)\in G\times X:\ g\cdot x=x\}. $$
On calcule $|E|$ de deux façons.
Première façon¶
En fixant $g$,
$$ |E| = \sum_{g\in G} |\operatorname{Fix}(g)|. $$
Deuxième façon¶
En fixant $x$,
$$ |E| = \sum_{x\in X} |\operatorname{Stab}(x)|. $$
Or
$$ |\operatorname{Stab}(x)| = \frac{|G|} {|\operatorname{Orb}(x)|}. $$
Dans chaque orbite $O$,
$$ \sum_{x\in O} |\operatorname{Stab}(x)| = |O| \frac{|G|}{|O|} = |G|. $$
Chaque orbite contribue donc exactement $|G|$.
Ainsi
$$ |E| = |G|\cdot |X/G|. $$
En comparant les deux expressions :
$$ \sum_{g\in G} |\operatorname{Fix}(g)| = |G|\cdot |X/G|, $$
d'où
$$ \boxed{ |X/G| = \frac1{|G|} \sum_{g\in G} |\operatorname{Fix}(g)| }. $$
À maîtriser sans notes¶
- définir $E$ ;
- premier comptage par $g$ ;
- second comptage par $x$ ;
- utiliser orbite-stabilisateur ;
- regrouper par orbites ;
- conclure.
Python / visualisation¶
Objectif¶
Explorer numériquement les coefficients binomiaux et faire apparaître le triangle de Pascal.
Modifier $n$ à la souris et observer :
- la symétrie des coefficients ;
- leur somme ;
- leur distribution ;
- les identités combinatoires suggérées.
Voir → manipuler → conjecturer → démontrer.
import math
import matplotlib.pyplot as plt
import ipywidgets as widgets
from ipywidgets import interact
@interact(
n=widgets.IntSlider(
min=1,
max=30,
step=1,
value=8,
description="n"
)
)
def explorer_binome(n=8):
coeffs = [
math.comb(n, k)
for k in range(n + 1)
]
print("Coefficients :")
print(coeffs)
print()
print("Somme =", sum(coeffs))
print("2^n =", 2**n)
plt.figure(figsize=(8, 4))
plt.bar(
range(n + 1),
coeffs
)
plt.xlabel("k")
plt.ylabel("C(n,k)")
plt.title(
f"Coefficients binomiaux pour n={n}"
)
plt.show()
Références¶
Hiérarchie documentaire utilisée¶
Rapports du jury de l'Agrégation interne de mathématiques
Référence prioritaire pour les attentes de l'épreuve, les points de vigilance et les exigences scientifiques.Agrég Maths en ligne / travaux de préparationnaires
Comparaison des plans, exercices, exemples et développements effectivement utilisés.Ressources personnelles et institutionnelles
Livres, PDF, polycopiés et ressources disponibles sur le VPS pour la vérification et l'approfondissement mathématique.
Bibliothèque personnelle prioritaire¶
X. Gourdon — Les maths en tête : Algèbre et probabilités
Référence principale pour combinatoire, permutations et probabilités finies.J.-É. Rombaldi — Mathématiques pour l'agrégation — Algèbre et géométrie
Référence pour groupes, actions et algèbre.L. T. Peccatte & L. Isenmann — L'oral à l'agrégation de mathématiques
Référence de préparation orale.J.-M. Garnier — Les mathématiques du CAPES
Référence complémentaire pour exercices élémentaires.
Documents sans ISBN¶
- Programme officiel.
- Rapports de jury.
- Polycopiés institutionnels présents sur le VPS.
Les chapitres/pages précis seront renseignés à partir des exemplaires réellement disponibles.
Références avec ISBN¶
À compléter uniquement à partir des ouvrages effectivement vérifiés dans la bibliothèque de travail.