A - Problèmes de dénombrement

Nous nous intéressons dans ce chapitre aux méthodes classiques de dénombrement d'ensembles finis. En conjonction avec les techniques destinées à prouver l'existence de certaines de ces structures finies, ces méthodes constituent la branche des mathématiques appelée "analyse combinatoire". Cette théorie intervient dans les calculs de probabilité rencontrés au lycée, chaque fois que le contexte équiprobable permet d'employer la formule

Lorsque l'on dépasse le cadre élémentaire des arrangements et des combinaisons, les méthodes de l'analyse combinatoire sont souvent difficiles (voir les exercices de l'activité 1). Nous nous contenterons de décrire quelques techniques de dénombrement, ceux-ci pouvant intervenir dans des problèmes où les probabilités ne jouent qu'un rôle mineur, voire pas de rôle du tout.

Nous rappelons ci-dessous les idées et les formules de dénombrement les plus classiques (à l'exception de l'avant-dernière, la formule du crible de Poincaré, que nous démontrons dans un cas particulier).

1 - Principes de comparaison

S'il existe une injection d'un ensemble E dans un ensemble fini F, alors E est lui aussi fini et Card E Card F. S'il existe une surjection d'un ensemble fini E dans un ensemble F, F est lui aussi fini et Card E Card F. S'il existe une bijection entre deux ensembles finis E et F, ces ensembles ont le même nombre d'éléments.

2 - Parties d'un ensemble

Le nombre de parties - ou sous-ensembles - d'un ensemble à n éléments est 2ⁿ.

3 - Applications

Le nombre d'applications d'un ensemble E à n éléments dans un ensemble F à p éléments est égal à pⁿ.

4 - Arrangements (ou injections) (ou p-listes)

Le nombre d'arrangements de p éléments distincts parmi n est égal à

(c'est aussi le nombre d'injections d'un ensemble à p éléments dans un ensemble à n éléments).

5 - Permutations

Le nombre de permutations d'un ensemble à n éléments est égal à n!.

6 - Combinaisons

Le nombre de combinaisons de p éléments parmi n (c'est-à-dire de sous-ensembles à p éléments dans un ensemble à n éléments) est égal à

(c'est le nombre de p-listes divisé par p! car chaque partie à p éléments peut être classée de p! manières, donnant ainsi naissance à p! p-listes distinctes).

7 - Formule du binôme de Newton

8 - Formule du crible de Poincaré

Si (A_i)_{i {1, , n}} est une famille finie de parties de E,

Cette formule est une généralisation de la formule classique

Card (A B) = Card (A) + Card (B) - Card (A B)

Elle se démontre par récurrence sur n. La démonstration générale est fastidieuse ; nous nous contenterons de montrer comment on passe de n = 2 (formule ci-dessus) à n = 3. On trouvera dans les activités 1 (exercices 6 et 7) et 2 (exercice XXX) des exemples d'application de la formule de Poincaré.

Card (A B C)	=	Card((A B) C)
	=	Card(A B) + Card(C) - Card((A B) C)
	=	Card(A) + Card(B) - Card(A B) + Card(C) - Card((A B) C)

Comme (A B) C = (A C) (B C),

Card ((A B) C) = Card (A C) + Card (B C) - Card ((A B) (B C))

D'autre part, (A B) (B C) = A B C. On obtient donc finalement

Card (A B C) = Card (A) + Card (B) + Card (C) - Card (A B)- Card (A C) - Card (B C) + Card (A B C)

qui est bien la formule souhaitée.

Evidemment, la formule du crible admet un cas particulier sensiblement plus simple, celui où les ensembles A_i sont deux à deux disjoints. Ils forment alors une stratification (ou partition) de A_i et la formule devient

Card (A₁ ... A_n) = Card (A₁) + ... + Card (A_n)

Il faut penser également que le nombre d'éléments du complémentaire de A dans E est égal à Card E - Card A. Cette remarque peut faciliter le calcul du nombre d'éléments d'une réunion quand la formule du crible s'applique difficilement. En effet, il est souvent plus facile de calculer le nombre d'éléments d'une intersection que celui d'une réunion (les conditions sont plus restrictives ; dans le cadre probabiliste on peut souvent utiliser de l'indépendance...).

Exemple - De combien de manières peut-on placer 16 pièces sur un échiquier 8 8 de sorte qu'une case noire au moins soit occupée (raisonner en passant au complémentaire ou en utilisant la formule du crible).

9 - Lemme du berger

Nous terminons par un résultat connu sous le nom de lemme du berger : si un ensemble E possède une partition en p sous-ensembles contenant chacun r éléments, Card E = pr. Par exemple, si un arbre possède huit branches et si au bout de chacune pendent quatre rameaux, le nombre total de rameaux est égal à trente-deux. Il résulte en particulier de ce lemme que, si les X_i sont des ensembles finis,

On utilise fréquemment ce lemme dans l'autre sens : si on connait Card E , et si E admet une partition en p sous-ensembles à r élements (un des nombres p et r est connu et pas l'autre), on en déduit celui des nombres p et r qu'on ne connaissait pas.

Exemple - Il y a A_n^p manières de choisir une p-liste ordonnée dans n éléments (par application directe du lemme du berger, mais p-1 fois au lieu d'une). Chaque partie à p éléments peut être ordonnée en p! p-listes distinctes. Donc il y a C_n^p = A_n^p /p! manières de choisir un sous-ensemble à p éléments dans n éléments.

On montre aussi en appliquant cette méthode que si E est un groupe fini à n éléments, le cardinal de tout sous-groupe de E divise n (théorème de Lagrange).

Exercice - En utilisant certains des résultats ci-dessus, donner une démonstration combinatoire (c'est-à-dire en raisonnant sur des cardinaux) des égalités