Combinatoire/Fiche/Formulaire

Fiche mémoire sur quelques formules

Cette fiche liste l’ensemble des formules présentes dans le cours. Elle résume également les principaux cas d’applications des 6 types de décomptes que nous avons envisagés.

Formules relatives aux factorielles

$0!=1$

$n!=(n-1)!\times n$

${\begin{aligned}{\frac {n!}{(n-k)!}}&={\frac {(n-k)!\times (n-k+1)\times (n-k+2)\times \cdots \times (n-1)\times n}{(n-k)!}}\\&=(n-k+1)\times (n-k+2)\times \cdots \times (n-1)\times n\end{aligned}}$

Arrangements

Début d’un théorème

Formule des arrangements sans répétition

Pour tous entiers n, k, le nombre d'arrangements sans répétition de k éléments d'un ensemble à n éléments, noté $A_{k}^{n}$, est :

$A_{n}^{k}={\frac {n!}{(n-k)!}}$ si $0\leq k\leq n$ et 0 sinon.

Ce cas correspond à :

• des tirages sans remise dont l’ordre est important de k objets parmi n objets ;
• des répartitions de k objets discernables dans n boîtes discernables, pouvant chacune contenir au maximum un objet ;
• des injections d'un ensemble de cardinal k vers un ensemble de cardinal n.

Fin du théorème

Début d’un théorème

Nombre d'arrangements avec répétition

Pour tous n, k ∈ ℕ, le nombre d'arrangements avec répétition de k éléments d'un ensemble à n éléments est égal à $n^{k}$.

Ce cas correspond à :

• des tirages, avec remise et dont l’ordre est important, de k objets parmi n objets ;
• des répartitions de k objets discernables dans n boîtes discernables ;
• des applications d'un ensemble de cardinal k vers un ensemble de cardinal n.

Fin du théorème

Permutations

Début d’un théorème

Nombre de permutations sans répétition

Pour tout n ∈ ℕ, le nombre de permutations sans répétition de n objets discernables est égal à

$A_{n}^{n}=n!$.

Ce cas correspond à :

• des tirages sans remise de n objets parmi n ;
• des classements de n objets ;
• des bijections entre deux ensembles E et F de cardinal n.

Fin du théorème

Début d’un théorème

Formule des permutations avec répétition

Le nombre n-uplets de k objets discernables $x_{1},\dots ,x_{k}$ avec chaque $x_{i}$ répété $n_{i}$ fois ($n_{i}\in \mathbb {N} ,\,n=\sum _{i=1}^{k}n_{i}$) est le coefficient multinomial

${\binom {n}{n_{1},n_{2},\ldots ,n_{k}}}={\frac {n!}{n_{1}!\,n_{2}!\ldots n_{k}!}}$.

Fin du théorème

Combinaisons

Début d’un théorème

Formule des combinaisons sans répétition

Pour tous entiers n et k, le nombre de combinaisons (sans répétition) de k éléments pris dans un ensemble à n éléments est :

${\binom {n}{k}}={\frac {A_{n}^{k}}{k!}}={\begin{cases}{\frac {n!}{k!\,(n-k)!}}&{\text{ si }}0\leq k\leq n\\0&{\text{ sinon.}}\end{cases}}$

Fin du théorème

C'est le nombre de parties de cardinal k d'un ensemble de cardinal n.

Début d’un théorème

Formule des combinaisons avec répétition

Pour tous entiers n > 0 et k, le nombre de $k$-combinaisons avec répétition dans un ensemble à n éléments est égal à

${\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}$.

Fin du théorème

C'est le nombre de $n$-uplets d'entiers naturels de somme $k$.