Table des matières

Combinatoire et dénombrement
Résumé

Combinatoire et dénombrement

Introduction

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.

Principes de base

Cardinal d'un ensemble

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.

Principe d'addition

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.

Principe de multiplication

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énombrement

Factorielle

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.

p-liste

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.

Permutation

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.

Arrangement

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.

Combinaison

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 $.

Résumé

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}