J'ai des problèmes de couples
Bonjour,
Un restaurant accueille $n$ couples mariés qui vont dîner autour d'une table $\textbf{ronde}$.
Le maître d'hôtel installe tout d'abord les dames en laissant une place entre chacune d'elles.
Maintenant que les dames sont installées, on demande de combien de façons on peut placer les messieurs de telle sorte qu'aucune dame ne soit à côté de son époux.
On notera $\mu(n)$ ce nombre de placements.
Calculer $\mu(13)$.
Comme dans tous les problèmes de couples, l'essentiel est de partir sur des bases solides, être d'accord sur les conventions, poser les bonnes définition ensemble.
Source: "Précis de concours"- Jean-Louis Roque-CERAM, Sophia Antipolis.
...
Un restaurant accueille $n$ couples mariés qui vont dîner autour d'une table $\textbf{ronde}$.
Le maître d'hôtel installe tout d'abord les dames en laissant une place entre chacune d'elles.
Maintenant que les dames sont installées, on demande de combien de façons on peut placer les messieurs de telle sorte qu'aucune dame ne soit à côté de son époux.
On notera $\mu(n)$ ce nombre de placements.
Calculer $\mu(13)$.
Comme dans tous les problèmes de couples, l'essentiel est de partir sur des bases solides, être d'accord sur les conventions, poser les bonnes définition ensemble.
Source: "Précis de concours"- Jean-Louis Roque-CERAM, Sophia Antipolis.
...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Est ce que le maître d’hôtel reconnait les dames des messieurs, et a-t-il le droit de choisir dans son ordre le monsieur qu'il va placer ?
On applique le principe d'inclusion-exclusion sur les ensembles de permutations, paramétrés par $i$, tels que $(i,\sigma(i))$ n'est pas dans $X$. On trouve la somme
$$\sum_{k=0}^n (-1)^k (n-k)! a_k \text{,}$$
où $a_k$ est le nombre de sous-ensembles $Y$ de $X$ de cardinal $k$ tels que si $(x,y)$ et $(x',y')$ sont dans $Y$, alors $x \neq x'$ et $y \neq y'$.
Pour calculer $a_k$ dans le cas particulier de la table ronde, on voit que ça revient à compter le nombre de manières de sélectionner $k$ éléments de $\Z/(2n)\Z$ sans jamais en avoir deux consécutifs (dessiner la matrice correspondant à $X$, cela donne des cases qui se suivent, avec un pas vers le bas, un vers la droite, etc.). Soit $Z^{2n}_k$ ce nombre.
On va mettre en bijection le nombre de manières de sélectionner $k$ éléments dans $\Z/N\Z$ sans jamais deux consécutifs, modulo une rotation, et le nombre de manières de sélectionner $k$ éléments dans $\Z/(N-k)\Z$, modulo une rotation. Pour passer du premier ensemble au deuxième, on retire chaque élément qui suit un élément sélectionné. Pour la bijection réciproque, on intercale un nouvel élément après chaque élément sélectionné.
On obtient $\frac{Z^N_k}{N} = \frac{\binom{N-k}{k}}{N-k}$, et donc $Z^N_k = \frac{N}{N-k} \binom{N-k}{k}$.
Une autre méthode pour calculer $Z^N_k$ consiste à dire que soit on sélectionne $0$, soit on ne le sélectionne pas, et on trouve $\binom{2n-k}{k} + \binom{2n-k-1}{k-1}$.
En remplaçant et en calculant avec un ordinateur, on a $\mu(13) = 775~596~313$.
La suite est sur l'OEIS http://oeis.org/A000179 et le problème sur Wikipédia https://en.wikipedia.org/wiki/Ménage_problem .
Voici comment l'auteur qui m'a inspiré cet exercice voit les choses. Son approche est un peu plus élémentaire (il me semble !).
On commence par numéroter de $1$ à $n$, dans le sens des aiguilles d'une montre, les dames.
On attribue à chaque monsieur le numéro de sa propre épouse.
On donne à chaque siège vide le numéro de la dame qui est à sa gauche.
On cherche à permuter convenablement les $n$ messieurs sur les $n$ places vides. Ces permutations doivent satisfaire les conditions suivantes:
$ \: \forall i \in 1,n, \: \sigma(i) \neq i.$
$ \: \forall i \in 1, n-1, \: \sigma(i) \neq i+1. $
$ \: \sigma(n) \neq 1.$
Tout cela ayant pour but d'empêcher que le monsieur numéro $i$ ne se retrouve à droite ou à gauche de son épouse.
$ \: E_{2i-1}=\{\sigma \: | \: \sigma(i)=i, \: i \in 1,n\}.$
$ \: E_{2i}=\{\sigma \: | \: \sigma(i)=i+1, \: i \in 1, n-1\}.$
$ \: E_{2n}=\{\sigma \: | \: \sigma(n)=1, \: i \in 1,n\}.$
Une permutation convenable ne doit appartenir à aucun de ces trois ensembles.
L'ensemble des placements convenables est donc:
\begin{equation}
\displaystyle \overline{E_1} \cap \overline{E_2} \cap \cdots \cap \overline{E_{2n}}
\end{equation}
Cela nous amène à la formule du crible par laquelle on calcule $\mu(n)$.
\begin{equation}
\displaystyle \mu(n)= n!-\sum_{k=1}^{2n}(-1)^{k-1} \sum_{1\leq i_1 < i_2 \leq \cdots < i_k \leq 2n} \: |E_{i_1} \cap E_{i_2} \cdots \cap E_{i_k}|
\end{equation}
Il y a des cas à distinguer avant d'appliquer un "lemme circulaire" (Kaplansky).
Le temps me manque un peu ce soir mais j'y reviendrai.
Avec seulement 13 couples, ce ne sont pas les possibilités qui manquent pour organiser son plan de table !
...
Par un calcul à la main, le début de ma suite à partir de $n = 3$ est: $1,\;2,\;14....$ et je ne vois ce début dans aucune suite donnée par les liens de @Champ-Pot-Lion ?
Ensuite en bas ''the simpler four-term recurrencs'' nous donne $A_5 = 12$ au lieu du $13$ qu'ils donnent.
Ensuite tu ne dis pas comment tu obtiens $14$, donc on ne peut rien te répondre. On peut lister explicitement les permutations valides :
Je n'ai pas envie d'étudier cette suite, parce que je ne crois pas encore à son exactitude.
$[2-4-1-5-3]$
$[4-5-1-2-3]$
$[3-4-1-5-2]$
$[4-3-1-5-2]$
$[2-4-5-1-3]$
$[2-5-4-1-3]$
$[3-4-5-1-2]$
$[3-5-4-1-2]$
$[4-3-5-1-2]$
$[2-3-4-5-1]$
$[3-4-5-2-1]$
$[3-5-4-2-1]$
$[4-3-5-2-1]$
$[5-3-4-2-1]$
Je pense n'avoir pas fait d'erreur (j'avais travaillé avec des lettres et des chiffres)
Merci.
On peut lister les $2n$ conditions de l'énoncé de la manière suivante:
$c_1$: le monsieur numéro $1$ est en première position.
$c_2$: le monsieur numéro $1$ est en deuxième position.
$c_3$: le monsieur numéro $2$ est en deuxième position.
$c_4$: le monsieur numéro $2$ est en troisième position.
.
.
.
$c_{2n-1}$: le monsieur numéro $n$ est en $n$-ième position.
$c_{2n}$: le monsieur numéro $n$ est en première position.
$\mu(n)$ est le nombre de permutations de $\{1, ..., n\}$ qui ne satisfont pas les $2n$ conditions ci-dessus.
On sait que le nombre de façons d'asseoir $n$ couples en alternant hommes et femmes et en faisant en sorte que personne ne soit assis à côté de sa moitié est: $2n!\mu(n)$.
Pour calculer $\mu(n)$, on applique le principe d'inclusion-exclusion. Il y a $n!$ façons d'installer les messieurs auxquelles il faut retrancher toutes les permutations qui rencontrent les $c_i$ conditions, pour $1 \leq i \leq 2n$.
Aucune permutation ne peut vérifier au moins deux conditions successives.
Ainsi, pour $k$ conditions $i_1, i_2, ..., i_k$ successives:
\begin{equation}
\displaystyle |E_{i_1} \cap E_{i_2} \cap \cdots \cap E_{i_k}|=0
\end{equation}
Si on impose un choix compris entre $n+1$ et $2n$ conditions, il est évident qu'au moins $2$ de ces conditions seront $\textbf{incompatibles}$ et le cardinal de l'intersection sera nul.
Dans le cas où $1 \leq k \leq n$, on a:
\begin{equation}
\displaystyle |E_{i_1} \cap E_{i_2} \cap \cdots \cap E_{i_k}| = (n-k)!
\end{equation}
Car une fois les $k$ images de la permutation fixées, on peut choisir sans contraintes les $(n-k)$ éléments restants. On peut donc réécrire la formule du crible avec un indice $k$ variant entre $1$ et $n$ uniquement.
\begin{equation}
\displaystyle \mu(n)= n! - \sum_{k=1}^n(-1)^{k-1} \sum_{1 \leq i_1 < i_2< \cdots <i_k \leq 2n} |E_{i_1} \cap E_{i_2} \cap \cdots \cap E_{i_k}|
\end{equation}
Il reste à connaître le nombre d'ensembles qui ne sont pas de cardinal $0$.
Selon le lemme circulaire, le nombre de manières de choisir $2$ conditions $\textbf{non-consécutives}$ parmi $2n$ est $\displaystyle {{2n-2} \choose 2} \frac{2n}{2n-2}$.
Et pour chacune de ces possibilités, il y a $(n-2)!$ façons de placer les $n-2$ messieurs restants.
Il en est de même pour $3, 4, \cdots k$ choix non-consécutifs.
Ainsi,
\begin{equation}
\displaystyle \mu(n)= n! - \frac{2n}{2n-1}{{2n-1} \choose {1}}(n-1)! + \frac{2n}{2n-2} {{2n-2} \choose {2}}(n-2)!+\frac{2n}{2n-3}{{2n-3} \choose {3}} (n-3)! +...
\end{equation}
...
Cordialement.