Factorielle

$n! = n \times (n-1) \times \cdots \times 2 \times 1 \qquad 0! = 1$

Exemples : $4! = 24$ , $5! = 120$ , $10! = 3\,628\,800$

Arrangements

Le nombre d’arrangements de $p$ éléments parmi $n$ (ordonnés, sans répétition) :

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

Exemple : Nombres de 3 chiffres distincts avec $\{1,2,3,4,5\}$ :

$A_5^3 = \frac{5!}{2!} = 60$

Le nombre de permutations de $n$ éléments (tous rangés, ordre compte) :

$P_n = n!$

Exemple : Anagrammes de MATHS : $5! = 120$

Le nombre de combinaisons de $p$ éléments parmi $n$ (non ordonnées, sans répétition) :

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

On note aussi $C_n^p$ .

Propriétés :

$\binom{n}{0} = \binom{n}{n} = 1 \qquad \binom{n}{1} = n \qquad \binom{n}{p} = \binom{n}{n-p}$

Exemples : $\binom{5}{2} = \frac{5!}{2! \cdot 3!} = 10$ ; $\binom{6}{3} = 20$

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

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
  1 5 10 10 5 1

$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$

Exemple : $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$

Si un événement peut se produire de $n_1$ façons, puis de $n_2$ façons indépendantes, le total est $n_1 \times n_2$ .

Exemple : Codes PIN de 4 chiffres : $10^4 = 10\,000$ possibilités.

Codes sans répétition : $10 \times 9 \times 8 \times 7 = A_{10}^4 = 5\,040$