En donnant un argument combinatoire (compter le même ensemble de deux façons différentes)

Démontrer une identité combinatoire en exhibant un ensemble dénombré de deux façons différentes qui correspondent aux deux membres.

L'objectif

Démontrer une identité combinatoire en exhibant un ensemble dénombré de deux façons différentes qui correspondent aux deux membres.

Le principe

Si deux expressions dénombrent le même ensemble, elles sont égales : on cherche donc un problème de comptage naturel dont les deux membres sont deux stratégies de résolution.

La méthode

1
Identifier un ensemble $E$ dont le cardinal est naturellement lié à l'un des membres de l'identité (souvent le membre le plus simple).
2
Compter $|E|$ d'une première façon pour retrouver le membre gauche, puis d'une seconde façon (en partitionnant ou en changeant l'ordre du choix) pour retrouver le membre droit.
3
Conclure : puisque les deux dénombrements comptent le même ensemble, les deux membres sont égaux.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Démontrer combinatoirement que $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ .

Étape 1 —

Identifier un ensemble

E

dont le cardinal est naturellement lié à l'un des membres de l'identité (souvent le membre le plus simple).

Soit $E$ l'ensemble de tous les sous-ensembles d'un ensemble $A$ à $n$ éléments. Clairement $|E| = 2^n$ (chaque élément est soit inclus, soit exclu).

Étape 2 —

Compter

|E|

d'une première façon pour retrouver le membre gauche, puis d'une seconde façon (en partitionnant ou en changeant l'ordre du choix) pour retrouver le membre droit.

On peut aussi partitionner $E$ selon la taille $k$ du sous-ensemble : il y a $\binom{n}{k}$ sous-ensembles de taille $k$ , donc $|E| = \sum_{k=0}^{n}\binom{n}{k}$ .

Étape 3 —

Conclure : puisque les deux dénombrements comptent le même ensemble, les deux membres sont égaux.

Les deux dénombrements donnent $|E|$ , donc $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ .

$\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$

Application guidée

Démontrer combinatoirement que $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (relation de Pascal).

Application autonome 1

Démontrer que $\displaystyle\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ (identité de Vandermonde) par double comptage.

Application autonome 2

Démontrer combinatoirement que $\displaystyle\sum_{k=0}^{n}k\dbinom{n}{k} = n \cdot 2^{n-1}$ .

Application autonome 3

Démontrer combinatoirement que $\dbinom{n}{k} = \dbinom{n}{n-k}$ .

Crée ton compte gratuit pour accéder à la fiche et aux exercices