Méthodes de dénombrement

Pour dénombrer des objets, il peut être utile de commencer par écrire quelques exemples au brouillon.

Si on peut identifier les objets avec ceux d’un ensemble de référence, on applique la formule associée pour calculer le cardinal de cet ensemble.

Si on ne considère qu’une partie d’un ensemble de référence, il peut être utile d’appliquer les formules liées aux opérations ensemblistes, lorsque cette partie se décompose en plusieurs sous-ensembles ou si le cardinal du complémentaire est plus facile à calculer, par exemple lorsque l’on considère des objets qui contiennent au moins un élément donné : le complémentaire est alors constitué des objets qui ne contiennent pas cet élément.

Sinon on peut appliquer le principe des choix successifs ou mettre en évidence une bijection entre l’ensemble des objets à dénombrer et un autre ensemble dont on calculera plus facilement le cardinal.

Ensembles de référence

Dans les formules suivantes, on considère un ensemble fini E de cardinal n et éventuellement un ensemble fini F.

Entiers

Entre deux entiers relatifs a et binclus, il y en a Card ([[a, b]]) = b − a + 1.

(Ne pas oublier le décalage, surtout dans le cas d’un intervalle [[0 ; n]].)

Couples

Formés d’un élément de E et d’un élément de F, il y en a Card (E × F) = Card E × Card F.

Listes

Avec k éléments de E donnés dans un ordre précis et avec répétitions éventuelles, il y en a Card (E^k) = (Card E)^k.

Arrangements

Avec k éléments de E donnés dans un ordre précis mais sans répétition, il y en a A_n^k = n!/(n − k)! = n × (n − 1) × … × (n − k + 1), ce produit ayant k facteurs.

Combinaisons

Avec k éléments de E donnés sans ordre précis et sans répétition, il y en a (k parmi n) = n!/(k! (n − k)!) = (n × (n − 1) × … × (n − k + 1)) / (1 × 2 × … × k), la fraction ayant autant de facteurs au numérateur qu’au dénominateur.

Parties

Formées d’éléments de E, données sans ordre ni répétition, y compris la partie vide et l’ensemble E lui-même, il y en a Card 𝓟(E) = 2ⁿ

Les applications entre deux ensembles finis peuvent être traités comme des listes de valeurs : Card(𝓕(E, F)) = (Card(F))^Card(E).

Les injections d’un ensemble fini dans un autre peuvent être traités comme des arrangements. En particulier, il y a n! permutations d’un ensemble avec n éléments.

Les suites finies de nombres strictement croissantes peuvent être traitées comme des combinaisons (l’ordre étant imposé par les valeurs, il n’est pas significatif).

Opérations ensemblistes

Si A et B sont deux parties finies d’un même ensemble, alors leur réunion et leur intersection sont finies également et Card(A ∪ B) = Card(A) + Card(B) − Card(A ∩ B).

Plus généralement, on dispose de la formule du crible de Poincaré : Card(⋃_i=1ⁿ A_i) = ∑_{S⊂⟦1 ; n⟧, S≠∅} (−1)^Card(S)−1 Card(⋂_i∈S A_i)

Si E est un ensemble fini alors toute partie A ⊂ E est finie ainsi que son complémentaire avec Card(E \ A) = Card(E) − Card(A).

Principe des choix successifs

Ce principe s’appuie sur le lemme des bergers. On essaie d’expliciter les choix successifs réalisés pour construire un exemple. Puis on dénombre les possibilités offertes pour chaque choix, en distinguant si nécessaire des cas en fonction des choix précédents.

Si les choix successifs peuvent s’enchainer sur une même ligne, il suffit de multiplier les nombres de possibilités pour chaque choix pour obtenir le nombre de constructions différentes. Sinon, on organise les choix dans un arbre et calcule le nombre de possibilités de chaque nœud en ajoutant celles de ses descendants directs.

Enfin, on vérifie que deux constructions différentes ne peuvent aboutir à un même objet. Si ce n’est pas le cas mais que le processus de construction répète un même nombre de fois chaque objet, il suffit de diviser le nombre de constructions par le nombre de répétitions pour obtenir le nombre d’objets.