Exercice 1 4434

Soient $n$ et $p \in ℕ$ . Proposer des preuves combinatoires¹¹ 1 Une preuve combinatoire est une justification réalisée par dénombrement. Par exemple, en calculant de deux façons différentes le cardinal d’un même ensemble. des formules:

(a)

$\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$
(b)

$(\binom{n}{n - p}) = (\binom{n}{p})$
(c)

$(\binom{n}{p}) + (\binom{n}{p + 1}) = (\binom{n + 1}{p + 1})$ .

Exercice 2 1533 Correction

(Formule de Chu-Vandermonde)

Soient $p, q \in ℕ$ et $n \in ⟦ 0; p + q ⟧$ . Proposer une démonstration par dénombrement de l’égalité

(\binom{p + q}{n}) = \sum_{k = 0}^{n} (\binom{p}{k}) (\binom{q}{n - k}) .

Solution

Soit $E$ un ensemble à $p + q$ éléments séparé en deux parties disjointes $E^{'}$ et $E^{''}$ de cardinaux $p$ et $q$ .
Il y a exactement $(\binom{p + q}{n})$ parties à $n$ éléments dans $E$ .
Or pour former une partie à $n$ élément de $E$ , on peut pour chaque $k \in ⟦ 0; n ⟧$ commencer par choisir $k$ éléments dans $E^{'}$ avant d’en choisir $n - k$ dans $E^{''}$ . Il y a $(\binom{p}{k}) (\binom{q}{n - k})$ possibilités pour chaque $k \in ⟦ 0; n ⟧$ puis au total $\sum_{k = 0}^{n} (\binom{p}{k}) (\binom{q}{n - k})$ possibilités d’où l’identité.

Exercice 3 4435

Soient $E$ un ensemble à $n$ éléments et $p$ un entier avec $1 \leq p \leq n$ . En dénombrant les couples $(A, x)$ constitués d’une partie $A$ de $E$ à $p$ éléments et d’un élément $x$ de $A$ , établir l’identité

(\binom{n}{p}) = \frac{n}{p} (\binom{n - 1}{p - 1}) .

[<] Composition d'un entier

Édité le 29-08-2023

Démonstrations combinatoires