Ascension Maths

I. Les deux principes fondamentaux

Dénombrer, c'est compter sans énumérer. Deux principes suffisent à construire tous les résultats du chapitre, et la difficulté est presque toujours de reconnaître lequel s'applique.

PropriétéPrincipe additif

Si des ensembles finis $A_1, A_2, \ldots, A_n$ sont deux à deux disjoints, alors

\text{Card}(A_1 \cup \cdots \cup A_n)=\text{Card}(A_1)+\cdots+\text{Card}(A_n)

Ce principe traduit le mot « ou » lorsque les cas s'excluent mutuellement.

PropriétéPrincipe multiplicatif

Pour deux ensembles finis $A$ et $B$ :

\text{Card}(A \times B)=\text{Card}(A) \times \text{Card}(B)

Ce principe traduit une succession de choix indépendants : si une première décision offre $p$ possibilités et la suivante $q$ , l'ensemble des décisions en offre $pq$ .

Exemple

Un menu propose $4$ entrées, $6$ plats et $3$ desserts. Le nombre de repas complets vaut $4 \times 6 \times 3 = 72$ .

Si l'on accepte un repas composé d'un plat seul ou d'un plat avec dessert, il faut cette fois additionner les deux cas, car ils s'excluent.

II. k-uplets et permutations

Définitionk-uplet

Un $k$ -uplet d'éléments d'un ensemble $E$ est une liste ordonnée de $k$ éléments de $E$ , les répétitions étant autorisées.

Si $E$ compte $n$ éléments, le nombre de $k$ -uplets vaut $n^k$ , par application répétée du principe multiplicatif.

PropriétéParties d'un ensemble

Un ensemble à $n$ éléments possède exactement $2^n$ parties.

En effet, construire une partie revient à décider, pour chacun des $n$ éléments, s'il est pris ou non : c'est un $n$ -uplet de $\{0\,;1\}$ .

DéfinitionFactorielle et permutations

Pour un entier naturel $n$ non nul, la factorielle de $n$ est le produit

n! = n \times (n-1) \times \cdots \times 2 \times 1

avec la convention $0!=1$ .

Une permutation d'un ensemble à $n$ éléments est un rangement ordonné de tous ses éléments. Il en existe exactement $n!$ .

Propriéték-uplets d'éléments distincts

Le nombre de $k$ -uplets d'éléments distincts d'un ensemble à $n$ éléments vaut

n \times (n-1) \times \cdots \times (n-k+1)=\frac{n!}{(n-k)!}

Chaque choix réduit d'une unité le nombre de possibilités suivantes.

Exemple

Un code de $4$ chiffres offre $10^4 = 10\,000$ possibilités. Si les chiffres doivent être tous différents, il n'en reste que $10 \times 9 \times 8 \times 7 = 5\,040$ .

III. Combinaisons

DéfinitionCoefficient binomial

Une combinaison de $k$ éléments d'un ensemble à $n$ éléments est une partie à $k$ éléments : l'ordre n'intervient pas.

Leur nombre se note $\binom{n}{k}$ et vaut, pour $0 \leqslant k \leqslant n$ :

\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!\,(n-k)!}

MéthodeAvec ou sans ordre

La question à se poser est toujours la même : l'ordre du tirage change-t-il le résultat ?

Pour un podium, oui : premier et deuxième ne sont pas interchangeables, il s'agit de $k$ -uplets distincts.

Pour une main de cartes ou une délégation, non : c'est une combinaison.

Le passage de l'un à l'autre se fait en divisant par $k!$ , qui est le nombre de façons d'ordonner les $k$ éléments choisis.

PropriétéValeurs et symétrie

\binom{n}{0}=1 \qquad \binom{n}{1}=n \qquad \binom{n}{2}=\frac{n(n-1)}{2} \qquad \binom{n}{k}=\binom{n}{n-k}

La symétrie s'explique sans calcul : choisir les $k$ éléments retenus revient à choisir les $n-k$ éléments écartés.

Exemple

Le nombre de mains de $5$ cartes dans un jeu de $32$ vaut

\binom{32}{5}=\frac{32 \times 31 \times 30 \times 29 \times 28}{5 \times 4 \times 3 \times 2 \times 1}=201\,376

IV. Relation et triangle de Pascal

PropriétéRelation de Pascal

Pour $1 \leqslant k \leqslant n-1$ :

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

Démonstration : Relation de Pascal, par le dénombrement

On considère un ensemble $E$ à $n$ éléments, et on fixe l'un d'eux, noté $a$ . Les parties à $k$ éléments de $E$ se répartissent en deux familles, sans recouvrement.

Celles qui contiennent $a$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, ce qui donne $\binom{n-1}{k-1}$ possibilités.

Celles qui ne contiennent pas $a$ : il faut choisir les $k$ éléments parmi les $n-1$ autres, ce qui donne $\binom{n-1}{k}$ possibilités.

Le principe additif donne alors la relation annoncée.

Démonstration : Somme des coefficients binomiaux

Montrons que

\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n

On compte de deux façons les parties d'un ensemble $E$ à $n$ éléments.

D'un côté, ce nombre vaut $2^n$ , puisque construire une partie revient à décider pour chaque élément s'il est pris ou non.

De l'autre, on peut regrouper les parties selon leur nombre d'éléments : il y a $\binom{n}{k}$ parties à $k$ éléments, et $k$ varie de $0$ à $n$ . Le principe additif donne la somme du membre de gauche.

Les deux comptages portant sur le même ensemble, ils sont égaux.

RemarqueLe triangle de Pascal

La relation de Pascal permet de construire les coefficients de proche en proche : chaque nombre est la somme des deux situés juste au-dessus de lui.

$n$	$k=0$	$1$	$2$	$3$	$4$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$1$	$4$	$6$	$4$	$1$

ExempleGénérer une ligne du triangle

def ligne_pascal(n):
    L = [1]
    for k in range(1, n + 1):
        L.append(L[k - 1] * (n - k + 1) // k)
    return L

La fonction utilise le passage d'un coefficient au suivant, ce qui évite de calculer des factorielles très grandes.

Combinatoire et dénombrement

Avant de commencer

À la fin du chapitre, tu sais

I. Les deux principes fondamentaux

II. k-uplets et permutations

III. Combinaisons

IV. Relation et triangle de Pascal

$n$	$k=0$	$1$	$2$	$3$	$4$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$1$	$4$	$6$	$4$	$1$

$n$	$k=0$	$1$	$2$	$3$	$4$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$1$	$4$	$6$	$4$	$1$

$n$	$k=0$	$1$	$2$	$3$	$4$
$0$	$1$
$1$	$1$	$1$
$2$	$1$	$2$	$1$
$3$	$1$	$3$	$3$	$1$
$4$	$1$	$4$	$6$	$4$	$1$