Le dénombrement consiste à compter des objets. Certains exercices de dénombrement se limitent à cette tâche : compter. Pour réussir efficacement et rapidement, il est essentiel de suivre une méthode rigoureuse plutôt que de compter de façon désordonnée.

L'analyse combinatoire regroupe justement les techniques utilisées pour compter les éléments d'un ensemble de manière structurée.

Par convention, on définit : $$\bbox[pink,5px] {0! = 1}$$

Cependant, ce résultat peut être démontré en utilisant la relation récurrente de la factorielle : $$n! = n \times (n-1)! \quad \text{pour } n \geq 1.$$

En appliquant cette relation pour $n = 1$ : $$1! = 1 \times (1-1)! = 1 \times 0!$$

Cela implique : $$1 = 1 \times 0! \quad \implies \quad 0! = 1.$$

Ainsi, la valeur $0! = 1$ est cohérente avec la définition récurrente de la factorielle.

Remarque : dans une situation où aucun élément n'est choisi ($p = 0$), on a : $$\binom{n}{0} = \frac{n!}{0! \cdot (n-0)!} = \frac{n!}{1 \cdot n!} = 1,$$ ce qui correspond intuitivement à une seule façon de ne rien choisir.

Proposition : Pour tout $n$, $$\sum_{k=0}^n \binom{n}{k} = 2^n.$$

Propriété : Relation de Pascal Pour $n$ et $p$ tels que $p \leq n$, $$\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}.$$

À partir de cette propriété, on déduit le triangle de Pascal, qui regroupe les valeurs de $\binom{n}{p}$ pour différents $n$ et $p$.

Notions de base

• Principes de comptage fondamentaux :
  • *Règle du produit* : multiplication des possibilités pour des choix successifs.
  • *Règle de la somme* : addition des possibilités pour des choix alternatifs.
• Principe d'inclusion-exclusion : comptage des éléments dans des ensembles qui se chevauchent.

Arrangements et permutations

• Arrangements sans répétition : Ordre important, éléments distincts

$$A_n^p = \frac{n!}{(n-p)!}$$

• Arrangements avec répétition : Chaque élément peut être choisi plusieurs fois

$$n^p$$

• Permutations : Arrangements de $n$ éléments sans condition particulière

$$n!$$

• Permutations avec répétition : Cas où certains éléments se répètent

$$\frac{n!}{n_1! n_2! \dots n_k!}$$

Combinaisons

• Combinaisons sans répétition : Choix de $p$ éléments parmi $n$, ordre non important

$$C_n^p = \binom{n}{p} = \frac{n!}{p!(n-p)!}$$

• Combinaisons avec répétition : Distribution de $p$ objets dans $n$ catégories

$$\binom{n+p-1}{p}$$

Propriétés avancées

• Identités combinatoires :
  • Symétrie des coefficients binomiaux : $$\binom{n}{p} = \binom{n}{n-p}$$
  • Relation de Pascal : $$\binom{n}{p} = \binom{n-1}{p} + \binom{n-1}{p-1}$$

• Triangle de Pascal et applications : calcul de coefficients binomiaux.
• Formules de récurrence : développement de calculs combinatoires avec itérations.

Exercices typiques

• Combien de façons de distribuer $n$ cadeaux à $p$ enfants ?
• Combien d'anagrammes d'un mot donné ?
• Combien de combinaisons possibles pour former une équipe de $k$ personnes parmi $n$ ?
• Nombre de chemins dans un quadrillage $m \times n$ en allant du coin inférieur gauche au coin supérieur droit.

Les critères sont : les éléments peuvent-ils être répétés ? l’ordre des éléments est-il à prendre en compte ?

\begin{tabular}{|l||c|c|} \hline
& Avec ordre & Sans ordre \\   \hline\hline
\rule[-0.4cm]{0cm}{1cm} Avec répétition  & $\textbf{B}_n^p = n^p$ & hors programme \\ \hline
\rule[-0.4cm]{0cm}{1cm} Sans répétition  & $\arr{n}{p} = {n! \over (n-p)!}$& $\comb{n}{p} = \frac{n!}{p!\cdot (n-p)!}$\\ \hline
\end{tabular}

Le Lotto : Il s'agit de choisir 7 nombres parmi 49. En effet, on ne peut obtenir plusieurs fois le même numéro lors d’un tirage : les éléments sont distincts ! De plus, l’ordre d’apparition des différents numéros n'a pas d'importance puisque sur les grilles, il y a des croix : seul le résultat global des 7 numéros compte et l’ordre n’a pas d’importance. On doit donc utiliser les combinaisons ! On dénombre le nombre de parties de 7 éléments de l'ensemble $\{1, \ldots, 49\}$ de cardinal 49 : il y a donc $\binom{49}{7}$ possibilités, soit 85\,900\,584.

En pratique :

1. Si les différentes étapes sont reliées par un “ET”, on multiplie.
2. Si les différentes étapes sont reliées par un “OU”, on additionne.

Exemples : On tire au hasard 5 cartes d'un jeu en comptant 32. Combien de tirages sont possibles où l'on ait…

1. Exactement trois rois ? $$C_4^3 \cdot C_{28}^2 = 1\,512$$ 2. Au moins trois rois ? $$C_4^3 \cdot C_{28}^2 + C_4^4 \cdot C_{28}^1 = 1\,540$$ 3. Deux $\heartsuit$ et trois $\diamondsuit$ ? $$C_8^2 \cdot C_8^3 = 1\,568$$

Voici le texte adapté pour une page DokuWiki avec les modifications demandées :

Ce sont les tirages dans une urne, la plupart des exercices pouvant se ramener à l'une des trois situations ci-dessous. On supposera que l'urne que l'on considère contient $n$ boules ayant toutes la même probabilité de sortie.

Si l'on effectue $p$ tirages successifs avec remise, il y a $n^p$ issues différentes possibles.

Si l'on effectue $p$ tirages successifs sans remise, il y a $A_n^p$ issues différentes possibles si l'on tient compte de l'ordre de sortie, et $C_n^p$ issues différentes possibles si l'on ne tient pas compte de cet ordre.

On se ramène au cas des tirages sans remise. On peut, au choix, considérer ou non que l'ordre a de l'importance, le tout étant de rester cohérent d'un bout à l'autre de l'exercice : si l'on dénombre l'univers des possibles en tenant compte de l'ordre, il faut tenir compte de l'ordre jusqu'à la fin de l'exercice ! Moyennant cette précaution élémentaire, les deux méthodes (ordre ou non) donneront les mêmes résultats en termes de probabilité.