🔢Dénombrement et combinatoire

Principe multiplicatif. Si une expérience se décompose en $k$ étapes successives, et si l'étape $1$ offre $n_1$ possibilités, l'étape $2$ en offre $n_2$, …, l'étape $k$ en offre $n_k$ (chaque nombre étant indépendant des choix précédents), alors le nombre total de résultats est :

$n_1\times n_2\times\cdots\times n_k.$

Un $p$-uplet (ou $p$-liste) d'un ensemble $E$ à $n$ éléments est une liste ordonnée de $p$ éléments de $E$, avec répétitions autorisées. Le nombre de $p$-uplets est :

$n^{\,p}.$

C'est le cas typique d'un tirage successif avec remise, ou d'un code à $p$ caractères choisis parmi $n$ symboles.

Pour compter avec le principe multiplicatif :

1. Découpe le choix en étapes successives.
2. Compte le nombre de possibilités à chaque étape.
3. Multiplie tous ces nombres.
4. Demande-toi si l'ordre compte (oui ici) et s'il y a remise (répétitions autorisées ⇒ $p$-uplet, donc $n^{\,p}$).

Combien de codes de $3$ chiffres (de $0$ à $9$) peut-on former ?

Chaque position offre $10$ choix indépendants (avec remise), donc : $10\times 10\times 10 = 10^{3} = 1000 \text{ codes.}$

⚠️ « Avec remise » et « l'ordre compte » ⇒ $p$-uplet ($n^p$). Si l'ordre ne compte pas ou s'il n'y a pas de remise, ce n'est PLUS $n^p$ : c'est un arrangement ou une combinaison.

Factorielle. Pour un entier $n\ge 1$, on note :

$n! = n\times(n-1)\times\cdots\times 2\times 1,$

et par convention $0!=1$. Ainsi $1!=1$, $2!=2$, $3!=6$, $4!=24$, $5!=120$, $6!=720$.

Permutation. Une permutation d'un ensemble à $n$ éléments est une façon d'ordonner ces $n$ éléments (les ranger les uns à la suite des autres, sans répétition). Le nombre de permutations de $n$ objets est :

$n!.$

Intuition : on a $n$ choix pour la première place, puis $n-1$ pour la deuxième, …, $1$ pour la dernière, d'où le produit.

Pour reconnaître une permutation :

1. Vérifie qu'on utilise tous les $n$ éléments.
2. Vérifie que l'ordre compte et qu'il n'y a pas de répétition.
3. Le résultat est alors $n!$.

De combien de façons peut-on ranger $5$ livres distincts sur une étagère ?

On ordonne les $5$ livres, donc c'est une permutation : $5! = 5\times 4\times 3\times 2\times 1 = 120.$

🧠 Retiens $0!=1$ (ce n'est pas $0$ !). Cette convention rend les formules d'arrangements et de combinaisons cohérentes.

Un arrangement de $p$ éléments parmi $n$ (avec $0\le p\le n$) est une liste ordonnée de $p$ éléments deux à deux distincts choisis dans un ensemble à $n$ éléments : c'est un tirage successif sans remise. Leur nombre est :

$A_n^{\,p}=n\times(n-1)\times\cdots\times(n-p+1)=\dfrac{n!}{(n-p)!}.$

Il y a exactement $p$ facteurs au numérateur, qui descendent de $n$ jusqu'à $n-p+1$. Le mot-clé est : ordre + sans remise.

Pour calculer un arrangement $A_n^{\,p}$ :

1. Vérifie que l'ordre compte et qu'il n'y a pas de remise.
2. Pars de $n$ et multiplie en descendant, en t'arrêtant après $p$ facteurs (le dernier est $n-p+1$).
3. (Ou bien applique $A_n^{\,p}=\dfrac{n!}{(n-p)!}$.)

Dans une course de $8$ chevaux, combien de podiums (1er, 2e, 3e) sont possibles ?

L'ordre compte, sans remise, $p=3$ parmi $n=8$ : $A_8^{\,3}=8\times 7\times 6 = 336.$

🔎 Une permutation est un arrangement particulier : $A_n^{\,n}=\dfrac{n!}{0!}=n!$. Et $A_n^{\,1}=n$.

Une combinaison de $k$ éléments parmi $n$ est un sous-ensemble (une partie) à $k$ éléments d'un ensemble à $n$ éléments : ici l'ordre ne compte pas et il n'y a pas de répétition. Leur nombre, noté $\binom{n}{k}$ (lire « $k$ parmi $n$ »), vaut :

$\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}.$

On passe de l'arrangement à la combinaison en divisant par $k!$, car chaque sous-ensemble de $k$ éléments peut être ordonné de $k!$ façons :

$\binom{n}{k}=\dfrac{A_n^{\,k}}{k!}.$

Cas particuliers : $\binom{n}{0}=1$, $\binom{n}{n}=1$, $\binom{n}{1}=n$.

Pour calculer $\binom{n}{k}$ :

1. Choisis le plus petit entre $k$ et $n-k$ (symétrie).
2. Écris $A_n^{\,k}=n(n-1)\cdots(n-k+1)$ au numérateur ($k$ facteurs).
3. Divise par $k!$.
4. Simplifie avant de multiplier pour éviter les gros nombres.

Combien de mains de $2$ cartes parmi $5$ ?

L'ordre ne compte pas, donc c'est une combinaison : $\binom{5}{2}=\dfrac{5\times 4}{2\times 1}=\dfrac{20}{2}=10.$

Autre exemple : $\binom{5}{3}=\dfrac{5\times 4\times 3}{3\times 2\times 1}=\dfrac{60}{6}=10$ (on retrouve $\binom{5}{2}$ par symétrie).

⚠️ Ne confonds pas arrangement et combinaison : « podium, classement, code » ⇒ ordre ⇒ arrangement ; « équipe, comité, main de cartes » ⇒ pas d'ordre ⇒ combinaison.

Les combinaisons vérifient deux propriétés essentielles.

Symétrie. Pour $0\le k\le n$ : $\binom{n}{k}=\binom{n}{n-k}.$ Choisir les $k$ éléments qu'on prend revient à choisir les $n-k$ qu'on laisse.

Relation de Pascal. Pour $1\le k\le n$ : $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}.$ Elle permet de construire le triangle de Pascal, où chaque terme est la somme des deux situés juste au-dessus :

$\begin{array}{cccccc}1\\ 1 & 1\\ 1 & 2 & 1\\ 1 & 3 & 3 & 1\\ 1 & 4 & 6 & 4 & 1\\ 1 & 5 & 10 & 10 & 5 & 1\end{array}$

La ligne $n$ donne les $\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}$. Enfin, la somme d'une ligne vaut $\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^{\,n}$ : c'est le nombre total de parties d'un ensemble à $n$ éléments.

⭐ Pour les curieux — pourquoi ça marche ? La relation de Pascal se voit d'un coup. Pour choisir $k$ éléments parmi $n$, fixons un élément témoin, disons Tom. Soit on prend Tom : il reste alors $k-1$ éléments à choisir parmi les $n-1$ autres, soit $\binom{n-1}{k-1}$ façons. Soit on laisse Tom : on choisit les $k$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k}$ façons. Ces deux cas n'ont aucun chevauchement et couvrent tout, donc on les additionne : $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}$. Quant à $\sum_{k=0}^{n}\binom{n}{k}=2^{\,n}$, c'est encore plus parlant : pour fabriquer une partie, on passe les $n$ éléments en revue et pour chacun on dit « dedans » ou « dehors », soit $2\times 2\times\cdots\times 2=2^{\,n}$ choix — et trier ces parties selon leur taille $k$ redonne la somme des $\binom{n}{k}$.

Pour utiliser le triangle de Pascal :

1. Démarre chaque ligne et chaque fin de ligne par $1$.
2. Chaque case = somme des deux cases au-dessus (relation de Pascal).
3. Lis $\binom{n}{k}$ à la ligne $n$, position $k$ (en comptant à partir de $k=0$).

Vérifions $\binom{4}{1}+\binom{4}{2}=\binom{5}{2}$ : $\binom{4}{1}+\binom{4}{2}=4+6=10=\binom{5}{2}.\;✓$

Et la symétrie : $\binom{5}{2}=\binom{5}{3}=10$. ✓

💡 La symétrie fait gagner du temps : pour $\binom{10}{8}$, calcule plutôt $\binom{10}{2}=\dfrac{10\times 9}{2}=45$.

Pour compter, il faut d'abord identifier la situation en se posant deux questions :

1. L'ordre compte-t-il ? (« podium, code, classement » ⇒ oui ; « comité, main, équipe » ⇒ non).
2. Y a-t-il répétition / remise ? (un même élément peut-il apparaître plusieurs fois ?).

Le tableau de synthèse :

$\bullet$ Ordre oui, répétition oui ⇒ $p$-uplet : $n^{\,p}$.

$\bullet$ Ordre oui, répétition non ⇒ arrangement : $A_n^{\,p}=\dfrac{n!}{(n-p)!}$.

$\bullet$ Ordre non, répétition non ⇒ combinaison : $\binom{n}{k}=\dfrac{n!}{k!\,(n-k)!}$.

$\bullet$ Cas particulier : on ordonne tout ($p=n$, sans répétition) ⇒ permutation : $n!$.

Pour choisir le bon outil :

1. Demande-toi si l'ordre compte.
2. Demande-toi s'il y a répétition possible.
3. Croise les deux réponses dans le tableau pour obtenir la formule à appliquer.

« Combien de podiums (1er, 2e, 3e) parmi $8$ ? » : ordre oui, répétition non ⇒ arrangement $A_8^{\,3}=336$.

« Combien d'équipes de $3$ parmi $8$ ? » : ordre non, répétition non ⇒ combinaison $\binom{8}{3}=56$.

🧭 Une même donnée ($3$ parmi $8$) donne $A_8^3=336$ ou $\binom{8}{3}=56$ selon que l'ordre compte ou non : c'est la question de l'ordre qui tranche.