Combinatoire et dénombrement

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.

Définition : Le cardinal d'un ensemble $ A $ est le nombre d'éléments contenus dans $ A $.

On le note : $ \text{card}(A). $

Exemple : Si $ A $ désigne l'ensemble des cartes qui constituent un jeu de 32 cartes, alors $ \text{card}(A) = 32 $.

Définition : On dit qu'un ensemble $ A $ est fini si $ \text{card}(A) $ n'est pas infini.

Proposition : Soient $ A $ et $ B $ deux ensembles finis disjoints, c'est-à-dire n'ayant aucun élément commun, tels que $ \text{card}(A) = n $ et $ \text{card}(B) = m $. Alors, le nombre de façons de prendre un élément dans $ A $ ou un élément dans $ B $ est égal à $ n + m $.

Cela se traduit ainsi : $$ A \cap B = \emptyset \implies \text{card}(A \cup B) = \text{card}(A) + \text{card}(B). $$

Exemple : Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. Je peux donc y choisir un livre de $ 20 + 10 = 30 $ façons différentes.

Proposition : Soient $ A $ et $ B $ deux ensembles finis tels que $ \text{card}(A) = n $ et $ \text{card}(B) = m $. Le nombre de façons de prendre un élément dans $ A $ et un élément dans $ B $ est égal à $ n \times m $.

Cela se traduit ainsi : $$ \text{card}(A \cap B) = \text{card}(A) \times \text{card}(B). $$

Exemple : Dans ma bibliothèque, il y a 20 romans et 10 bandes dessinées. Je souhaite prendre un livre de chaque sorte. Il y a donc $ 20 \times 10 = 100 $ possibilités.

Le principe multiplicatif peut se représenter sous la forme d'un arbre des possibilités ou d'un tableau avec $ n $ colonnes et $ m $ lignes, comportant $ n \times m $ cellules.

Définition : La factorielle d'un nombre entier $ n $ est définie par : $$ n! = 1 \times 2 \times 3 \times \cdots \times (n-1) \times n. $$

Exemple : $$ 5! = 1 \times 2 \times 3 \times 4 \times 5 = 120. $$

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.

Définition : Soient $ n $ et $ p $ deux entiers naturels non nuls tels que $ p \leq n $, et soit $ E $ un ensemble à $ n $ éléments. Une p-liste de $ E $ est une liste ordonnée de $ p $ éléments pris parmi les $ n $ éléments de $ E $.

Exemple : Un digicode à 4 chiffres est une 4-liste de l'ensemble $ \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $. La 4-liste $ \{1, 1, 1, 0\} $ est différente de la 4-liste $ \{0, 1, 1, 1\} $.

Proposition : Le nombre de $ p $-listes prises dans un ensemble à $ n $ éléments est $ n^p $.

Exemple : Il y a $ 10^4 = 10000 $ possibilités pour un digicode composé de 4 chiffres.

Définition : Soit $ E $ un ensemble à $ n $ éléments, avec $ n \in \mathbb{N}_0 $. Une permutation de $ E $ est un ensemble composé des $ n $ éléments de $ E $.

Exemple : Si $ E = \{1, 2, 3\} $, alors $ F = \{2, 3, 1\} $ est une permutation de $ E $.

Remarque : $ E $ est une permutation de $ E $.

Proposition : Il y a $ n! $ permutations d'un ensemble à $ n $ éléments.

Définition : Un arrangement de $ p $ éléments dans un ensemble $ E $ est une $ p $-liste d'éléments distincts.

Exemple : Le podium d'une course à 20 participants est un arrangement composé du premier, du deuxième et du troisième.

Proposition : Le nombre d'arrangements de $ p $ éléments parmi $ n $ est : $$ A_n^p = \frac{n!}{(n-p)!} = n \times (n-1) \times \cdots \times (n-p+1). $$

Exemple : $ A_{20}^3 = 20 \times 19 \times 18 = 6840 $. Il y a donc 6840 podiums possibles pour une course à 20 participants.

Définition : Une combinaison de $ p $ éléments dans un ensemble $ E $ est un ensemble non ordonné de $ p $ éléments pris parmi $ n $.

Exemple : Sur un jeu de 32 cartes, une main de 5 cartes est une combinaison.

Proposition : Le nombre de combinaisons de $ p $ éléments parmi $ n $ est : $$ \binom{n}{p} = \frac{n!}{p!(n-p)!}. $$

Autre notation : $C_n^p = \dfrac{n!}{p!(n-p)!}$

Exemple : $ \binom{32}{5} = \frac{32 \times 31 \times 30 \times 29 \times 28}{5!} = 201376 $. Il y a donc 201376 mains de 5 cartes possibles dans un jeu de 32 cartes.

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.

Type	Ordre	Modèle	Exemples
p-liste	oui	tirage avec remise	digicode
Permutation	oui	tirage sans remise	anagramme
Arrangement $ A_n^p $	oui	tirage sans remise	podium d'une course
Combinaison $C_n^p$ ou $ \binom{n}{p}$	non	tirage sans remise	main dans un jeu de cartes

source pst-eucl

diagramme_formules.tex

\documentclass[pstricks,border=6pt]{standalone}
\usepackage{pst-eucl}
\usepackage[utf8]{inputenc} 
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{amsmath,amssymb}
\usepackage[bitstream-charter]{mathdesign}
\author{F. Lancereau}
\begin{document}
\begin{pspicture}(0,0)(17,10)
%\psgrid
\psset{nodesep=4pt}
\rput[c](8,9){\rnode{A}{\psframebox{Les $p$ éléments sont distincts 2 à 2}}}
\rput[c](6,7){\rnode{B}{\psframebox{l'ordre est important}}}
\rput[c](13.5,7){\rnode{C}{\psframebox{p-listes}}}
\ncline{-}{A}{B} % \ncline{->}
\ncput*{oui}
\ncline{-}{A}{C}
\ncput*{non}
\rput[c](3,5){\rnode{D}{\psframebox{$n=p$ ?}}}
\rput[c](9,5){\rnode{E}{\psframebox{combinaisons}}}
\ncline{-}{B}{D}
\ncput*{oui}
\ncline{-}{B}{E}
\ncput*{non}
\rput[c](13.5,5){\rnode{F}{\psframebox{$n^p$}}}
\ncline{-}{C}{F}
\rput[c](2,3){\rnode{G}{\psframebox{permutations}}}
\rput[c](5,3){\rnode{H}{\psframebox{arrangements}}}
\rput[c](9,3){\rnode{I}{\psframebox{$C^p_n$}}}
\rput[c](13.5,3){\rnode{J}{{{\begin{minipage}{0.4\linewidth}
\begin{itemize}
\item un tirage avec remise
\item un lancer successif d'un dé, d'une pièce
\end{itemize} 
\end{minipage}}}}}
\ncline{-}{D}{G}
\ncput*{oui}
\ncline{-}{D}{H}
\ncput*{non}
\ncline{-}{E}{I}
\ncline{-}{F}{J}
\rput[c](2,1){\rnode{K}{\psframebox{$n!$}}}
\rput[c](5,1){\rnode{L}{\psframebox{$A^p_n$}}}
\rput[c](9,1){\rnode{M}{{\begin{minipage}{0.5\linewidth}
\begin{itemize}
\item un tirage simultané
\item une main d'un jeu de cartes
\end{itemize} 
\end{minipage}}}}
\ncline{-}{G}{K}
\ncline{-}{H}{L}
\ncline{-}{I}{M}
\end{pspicture}
\end{document}

Combinatoire et dénombrement

Introduction

Principes de base

Cardinal d'un ensemble

Principe d'addition

Principe de multiplication

Dénombrement

Factorielle

p-liste

Permutation

Arrangement

Combinaison

Résumé