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.

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é