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$

Permutations

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

$P_n = n!$

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

Combinaisons

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$

Triangle de Pascal

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

Formule du binôme de Newton

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

Arbre de dénombrement

flowchart TD
    D["Départ"] --> A1["Choix 1 : A"]
    D --> A2["Choix 1 : B"]
    D --> A3["Choix 1 : C"]
    A1 --> B1["Choix 2 : X"]
    A1 --> B2["Choix 2 : Y"]
    A2 --> B3["Choix 2 : X"]
    A2 --> B4["Choix 2 : Y"]
    A3 --> B5["Choix 2 : X"]
    A3 --> B6["Choix 2 : Y"]
    B1 --> R1["A-X"]
    B2 --> R2["A-Y"]
    B3 --> R3["B-X"]
    B4 --> R4["B-Y"]
    B5 --> R5["C-X"]
    B6 --> R6["C-Y"]

3 choix au niveau 1 × 2 choix au niveau 2 = 6 chemins au total.

Principe des tiroirs (ou dénombrement par cas)

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$