Théorie > Combinatoire > Dénombrement (suite)


Général

Introduction Chapitre entier

Points théoriques

Comptage direct Bijection Inclusion-exclusion Récurrence

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6

Comptage direct

Beaucoup de problèmes de combinatoire consistent à dénombrer les différentes possibilités d'un événement. Par exemple, on rencontre souvent des problèmes du type du problème suivant.

Exemple : Quel est le nombre de manières d'asseoir $n$ couples autour d'une table ronde de $2n$ places, les hommes et les femmes devant être alternés?

Face à un tel problème, l'envie la plus naturelle est de vouloir utiliser les formules donnant le nombre de permutations, d'arrangements ou de combinaisons. Il faut alors trouver la façon la plus simple de dénombrer les possibilités. Il est pour cela primordial que la situation soit bien claire et il faut à tout prix tâcher de compter les possibilités de manière logique et ordonnée. Voici trois façons de procéder pour résoudre cet exemple.

  • La manière la plus intuitive pour compter le nombre de façons de placer des gens autour d'une table est peut-être d'essayer de placer les convives un à un et d'évaluer le nombre de choix possibles à chaque placement. Il est tout de même préférable de se simplifier le comptage et donc de placer les personnes dans un ordre logique. On peut donc par exemple placer toutes les femmes et puis seulement tous les hommes, ou encore placer les couples un à un (c'est-à-dire alterner le placement d'un homme avec le placement d'une femme). Procédons de cette dernière manière. Pour le premier couple, on a bien sûr $2n$ places possibles pour l'homme. Puisqu'il faut alterner les hommes et les femmes, il reste alors $n$ places disponibles pour la femme. Pour le deuxième couple, on a $(n-1)$ choix restants pour l'homme et, de même, $(n-1)$ choix pour la femme. On continue ainsi de suite jusqu'au dernier couple, où il n'y a plus qu'une place disponible pour l'homme ainsi qu'une place pour la femme. On voit bien sûr que cette méthode de placement fonctionnera toujours, en ce sens que le placement final sera alterné et que l'on peut atteindre tous les placements possibles. Il ne reste alors plus qu'à multiplier tous les choix que nous avons eu pour obtenir le nombre total de possibilités :
    $$2n \cdot n \cdot (n-1) \cdot (n-1) \cdot (n-2) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 2 \cdot 1 \cdot 1.$$ Il suffit alors de réordonner les termes différemment pour obtenir la formule finale
    $$2 (n!)^2.$$

  • La méthode précédente ne fonctionnera cependant pas toujours. Il se peut en effet que le nombre de possibilités lors du placement d'une personne dépende des précédents placements : il n'est alors pas possible de procéder de cette manière. Il est donc bon de réussir à voir les choses autrement. Au lieu de placer les convives un à un, on peut par exemple plutôt considérer les sièges un à un et décider pour chacun qui y placer. Si nous considérons les sièges dans l'ordre, alors il y aura $2n$ possibilités pour le premier siège (puisque quiconque peut s'y placer), puis $n$ pour le deuxième (il faut placer quelqu'un du sexe opposé au premier), puis $(n-1)$ pour le troisième,... On obtient de cette manière exactement les mêmes termes que dans la méthode précédente, ce qui donne évidemment la même réponse finale.

  • On peut également, au lieu d'effectuer des placements un par un, essayer de directement appliquer les formules de dénombrement pour évaluer le nombre de configurations possibles. Si on numérote les places de $1$ à $2n$, on a tout d'abord deux possibilités : mettre les femmes sur les places paires ou sur les places impaires. Quitte à multiplier le résultat par $2$ à la fin, on peut décider que les femmes seront placées sur les places paires. Alors, le nombre de façons de disposer les $n$ femmes sur les $n$ places qui leur sont accordées est simplement le nombre de permutations de $n$ objets (ici les femmes, quoiqu'il ne faut pas considérer les femmes comme des objets :-)), c'est-à-dire $n!$. De la même façon, il y a $n!$ manières de permuter les hommes, et on a donc au final un nombre de possibilité égal à
    $$2(n!)^2.$$

Passage au complémentaire

Parfois, un comptage direct n'est pas possible, mais une simple transformation du problème permet de le résoudre : passer au problème complémentaire. Par exemple, face au problème suivant :

Exemple : Quel est le nombre de manières d'asseoir $n$ couples autour d'une table ronde de $2n$ places de sorte qu'il y ait au moins deux personnes du même sexe l'une à côté de l'autre?

Il ne semble pas faisable d'effectuer un comptage comme dans l'exemple précédent. Une idée simple est alors de vouloir compter les manières de s'asseoir qui ne respectent pas ces conditions. On se rend vite compte que cela n'arrive que si les hommes et les femmes sont alternés : on est donc ramenés au problème précédent! Le nombre recherché est donc le nombre total de manières de s'asseoir, qui n'est autre que $(2n)!$ (le nombre de permutations de $2n$ objets), moins le résultat précédent $2(n!)^2$, c'est-à-dire
$$(2n)! - 2(n!)^2.$$