6.4 Le problème des ménages

Le problème des ménages est l’un des classiques de la combinatoire. Posé originalement par Lucas [Lucas] en 1891, ce n’est qu’ en 1934 que Touchard [Touchard] en fourni une première formule explicite, mais sans aucune démonstration. La première démonstration de la formule de Touchard est donné en 1943 par Kaplansky [Kaplansky]. La démonstration de Kaplansky reste cependant trop difficile pour notre cours. Heureusement pour nous, en 1986, Bogart et Doyle [BogartDoyle] en donne une démonstration largement simplifié dans leur article «Non-Sexist Solution of the Menage Problem». Malgré tout, c’est l’approche du livre de Beeler [Beeler] que nous vous présentons ici. Le problème des ménages s’énonce comme suit:

De combien de façon peut-on assoir n\displaystyle n couples autour d’une table ronde de sorte que les hommes et les femmes alternes et sans qu’aucun des hommes ne soient assis à côté de son épouse ?

Théorème 6.4.1:

Placer des dominos. Le nombre de façons de placer k\displaystyle k dominos 2×1\displaystyle 2\times 1 sur un quadriller n×1\displaystyle n\times 1 est (n−kk)\displaystyle\binom{n-k}{k}.

Démonstration.

L’idée est de remarquer qu’en plaçant k\displaystyle k dominos, nous occuperons un total de 2⁢k\displaystyle 2k cases ce qui signifie que n−2⁢k\displaystyle n-2k cases resteront libre. Le problème revient donc à compter le nombre de façon d’ordonner k\displaystyle k dominos et n−2⁢k\displaystyle n-2k cases vide, ce qui est l’équivalent du problème du MISSISSIPPI. On a donc: (k+n−2⁢k)!k!⁢(n−2⁢k)!=(n−kk)\displaystyle\frac{(k+n-2k)!}{k!(n-2k)!}=\binom{n-k}{k} possibilités. ∎

Théorème 6.4.2:

Choisir l’emplacement des couples. Le nombre de façon de choisir l’emplacement de k\displaystyle k couples assis ensemble sur une table ronde contenant 2⁢n\displaystyle 2n chaises identifié de 1\displaystyle 1 à 2⁢n\displaystyle 2n est 2⁢n2⁢n−k⁢(2⁢n−kk)\displaystyle\frac{2n}{2n-k}\binom{2n-k}{k}. Attention, ici nous ne plaçons pas les couples, mais choisissons uniquement les emplacements où seront placé des couples.

Démonstration.

L’idée ici revient à utiliser la méthode de l’élément distingué en combinaison avec le théorème précédent. Fixons la chaise numéro 1\displaystyle 1. On remarque donc qu’un membre d’un couple peut occuper cette chaise, ou la chaise peut être laissé vide. SI la chaise est occupé, alors l’autre membre du couple doit être assis sur la chaise 2\displaystyle 2 ou sur la chaise 2⁢n\displaystyle 2n. Nous avons donc trois cas à traiter.

  1. 1.
    ​

    Supposons que les chaises 1\displaystyle 1 et 2\displaystyle 2 sont occupées par un même couple. Il nous reste donc k−1\displaystyle k-1 couples à placer sur les 2⁢n−2\displaystyle 2n-2 chaises restante. Remarquez que maintenant que le cercle est coupé, il s’agit en fait du même problème que le problème des dominos que nous avons traité dans le théorème précédent. On a donc ((2⁢n−2)−(k−1)k−1)=(2⁢n−k−1k−1)\displaystyle\binom{(2n-2)-(k-1)}{k-1}=\binom{2n-k-1}{k-1} possibilités.

  2. 2.
    ​

    Supposons que les chaises 1\displaystyle 1 et 2⁢n\displaystyle 2n sont occupée par un même couple. Dans ce cas, le problème est essentiellement identique à ce que nous venons de faire. Le nombre de possibilités est donc (2⁢n−k−1k−1)\displaystyle\binom{2n-k-1}{k-1}.

  3. 3.
    ​

    Supposons finalement que la chaise 1\displaystyle 1 est libre. Dans ce cas, le cercle est à nouveau brisé et il nous faut placer les k\displaystyle k couples sur 2⁢n−1\displaystyle 2n-1 chaise. En applicant à nouveau le théorème précédent on a donc ((2⁢n−1)−kk)=(2⁢n−k−1k)\displaystyle\binom{(2n-1)-k}{k}=\binom{2n-k-1}{k} possibilités.

Maintenant, il ne nous reste plus qu’à additionner les trois cas, ce qui nous donne:

2⁢(2⁢n−k−1k−1)+(2⁢n−k−1k)\displaystyle\displaystyle 2\binom{2n-k-1}{k-1}+\binom{2n-k-1}{k} =\displaystyle\displaystyle= 2⁢(2⁢n−k−1)!(k−1)!⁢(2⁢n−2⁢k)!+(2⁢n−k−1)!k!⁢(2⁢n−2⁢k−1)!\displaystyle\displaystyle\frac{2(2n-k-1)!}{(k-1)!(2n-2k)!}+\frac{(2n-k-1)!}{k% !(2n-2k-1)!}
=\displaystyle\displaystyle= 2⁢k⁢(2⁢n−k−1)!k!⁢(2⁢n−2⁢k)!+(2⁢n−2⁢k)⁢(2⁢n−k−1)!k!⁢(2⁢n−2⁢k)!\displaystyle\displaystyle\frac{2k(2n-k-1)!}{k!(2n-2k)!}+\frac{(2n-2k)(2n-k-1)% !}{k!(2n-2k)!}
=\displaystyle\displaystyle= 2⁢n⁢(2⁢n−k−1)!k!⁢(2⁢n−2⁢k)!\displaystyle\displaystyle\frac{2n(2n-k-1)!}{k!(2n-2k)!}
=\displaystyle\displaystyle= 2⁢n2⁢n−k⁢(2⁢n−kk)\displaystyle\displaystyle\frac{2n}{2n-k}\binom{2n-k}{k}

∎

Théorème 6.4.3:

Problème des ménages. Le nombre de façons d’assoir n\displaystyle n couples autour d’une table ronde de sorte que les hommes et les femmes alternes et sans qu’aucun des hommes ne soient assis à côté de son épouse est donné par la formule suivante:

Mn=(n−1)!⁢∑i=0n(−1)i⁢2⁢n2⁢n−i⁢(2⁢n−ii)⁢(n−i)!\displaystyle M_{n}=(n-1)!\sum_{i=0}^{n}(-1)^{i}\frac{2n}{2n-i}\binom{2n-i}{i}% (n-i)!
Démonstration.

La solution est maintenant une simple application du principe d’inclusion-d’exclusion, suivi d’une application du principe d’équivalence. Pour trouver le nombre de façon qu’au moins i\displaystyle i couples soient assis ensembles, nous avons:

  1. 1.
    ​

    Premièrement, on choisit l’emplacement des hommes et l’emplacement des femmes, ce qui peut être fait de 2\displaystyle 2 façons.

  2. 2.
    ​

    On choisit les i\displaystyle i couples qui seront au bon endroit, ce qui peut être fait de (ni)\displaystyle\binom{n}{i} façons.

  3. 3.
    ​

    On choisit l’emplacement des i\displaystyle i couples, ce qui peut être fait de 2⁢n2⁢n−i⁢(2⁢n−ii)\displaystyle\frac{2n}{2n-i}\binom{2n-i}{i} façons d’après le théorème précédent.

  4. 4.
    ​

    On place les i\displaystyle i couples, ce qui peut être fait de i!\displaystyle i! façons.

  5. 5.
    ​

    On place le reste des hommes, puis le reste des femmes, ce qui peut être fait de [(n−i)!]2\displaystyle[(n-i)!]^{2} façons.

Le nombre de façons d’avoir au moins i\displaystyle i couples assis ensemble est donc 2⁢(ni)⁢2⁢n2⁢n−i⁢(2⁢n−ii)⁢i!⁢[(n−i)!]2\displaystyle 2\binom{n}{i}\frac{2n}{2n-i}\binom{2n-i}{i}i![(n-i)!]^{2}. On applique ensuite le principe d’inclusion-exclusion, puis on divise par 2⁢n\displaystyle 2n pour tenir compte des rotations de la table, ce qui nous donne finalement:

Mn\displaystyle\displaystyle M_{n} =\displaystyle\displaystyle= 22⁢n⁢∑i=0n(−1)i⁢(ni)⁢2⁢n2⁢n−i⁢(2⁢n−ii)⁢i!⁢[(n−i)!]2\displaystyle\displaystyle\frac{2}{2n}\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\frac{% 2n}{2n-i}\binom{2n-i}{i}i![(n-i)!]^{2}
=\displaystyle\displaystyle= 1n⁢∑i=0n(−1)i⁢n!⁢2⁢n2⁢n−i⋅(2⁢n−ii)⁢(n−i)!\displaystyle\displaystyle\frac{1}{n}\sum_{i=0}^{n}(-1)^{i}n!\frac{2n}{2n-i}% \cdot\binom{2n-i}{i}(n-i)!
=\displaystyle\displaystyle= (n−1)!⁢∑i=0n(−1)i⁢2⁢n2⁢n−i⁢(2⁢n−ii)⁢(n−i)!\displaystyle\displaystyle(n-1)!\sum_{i=0}^{n}(-1)^{i}\frac{2n}{2n-i}\binom{2n% -i}{i}(n-i)!

∎

À partir du théorème précédent, on peut construire le tableau ci-dessous contenant la valeur de Mn\displaystyle M_{n} pour de petites valeurs de n\displaystyle n:

n\displaystyle n 1\displaystyle 1 2\displaystyle 2 3\displaystyle 3 4\displaystyle 4 5\displaystyle 5 6\displaystyle 6 7\displaystyle 7
Mn\displaystyle M_{n} 0\displaystyle 0 0\displaystyle 0 2\displaystyle 2 12\displaystyle 12 312\displaystyle 312 9600\displaystyle 9600 416 880\displaystyle 416\leavevmode\nobreak\ 880