6.2 Le problème des rencontres ‣ Chapitre 6 Chapeaux, rencontres et tables rondes ‣ Combinatoire 1

Il existe de nombreuses version du problème des rencontres. Dans certain cas, il s’agit d’une simple réécriture du problème des chapeaux, mais celui qui nous intéresse ici en est en fait une généralisation. Il s’énonce comme suit:

Lors d’une soirée échangiste, $\displaystyle n$ couples sont invités. En arrivant, chaque homme dépose sa montre dans un bol. Lorsque tous les couples sont présents, chaque femme pige une montre qui déterminera avec quel homme elle passera la soirée. De combien de façons différentes exactement $\displaystyle k$ des $\displaystyle n$ femmes peuvent se voir assigner l’homme avec lequel elles sont arrivées ?

La solution du problème est en fait très similaire au problème des chapeaux que nous avons rencontré dans la section précédente. On choisit d’abord les $\displaystyle k$ couples qui resteront inchangé, puis on effectue un dérangement des $\displaystyle n-k$ couples restant. En dénotant la solution du problème par $\displaystyle D_{n,k}$ , on obtient donc la solution suivante:

\displaystyle D_{n,k}=\binom{n}{k}D_{n-k}=\binom{n}{k}\sum_{i=0}^{n-k}\frac{(-% 1)^{i}(n-k)!}{i!}=\sum_{i=0}^{n-k}\frac{(-1)^{i}n!}{i!\leavevmode\nobreak\ k!}

En particulier, on remarque que $\displaystyle D_{n,0}=D_{n}$ .

Dans le cas particulier où $\displaystyle 5$ couples sont présent, le nombre de façon qu’exactement $\displaystyle 2$ couples restent inchangé est donc:

\displaystyle D_{5,2}=\sum_{i=0}^{3}\frac{(-1)^{i}5!}{i!\leavevmode\nobreak\ 2% !}=\frac{5!}{0!\leavevmode\nobreak\ 2!}-\frac{5!}{1!\leavevmode\nobreak\ 2!}+% \frac{5!}{2!\leavevmode\nobreak\ 2!}-\frac{5!}{3!\leavevmode\nobreak\ 2!}=60-6% 0+30-10=20

Ce qui peut aussi être obtenu plus facilement dans le cas où nous connaissons déjà la valeur de $\displaystyle D_{3}$ par la formule suivante:

\displaystyle D_{5,2}=\binom{5}{2}D_{3}=10\cdot 2=20