Problème des ménages

Conservando su título original propuesto por el matemático francés François Édouard Anatole Lucas (1842-1891), en Théorie des nombres, Gauthier-Villars, Paris, 1891, el problema pretende contar el número de formas en las que puedes sentar a una mesa redonda $n$ parejas de comensales de forma que no coincida junta una pareja.

Por ejemplo, consideremos 3 parejas, $A_1A_2$, $B_1B_2$ y $C_1C_2$ y las sentamos en una mesa circular de esta forma:

pretendiendo no sentar a nadie al lado de su pareja. La pregunta sería: ¿de cuántas formas podemos sentarlas sin que coincidan  $A_1A_2$ o $B_1B_2$ o $C_1C_2$ al lado?

Un problema equivalente había sido formulado, independientemente, por el matemático escocés Peter Guthrie Tait, que estaba estudiando la teoría de nudos, en On knots, i, ii, iii, in Scientific Papers, pages 273-347. Cambridge Univ. Press, Cambridge, 1898.

La primera fórmula explícita que daba el número fue publicada por el francés Jacques Touchard en 1934,
$$M_{n}=2\cdot n!\sum _{{k=0}}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.$$
Aunque no dio su prueba. Tendríamos que esperar a 1943 para que Kaplansky (Solution of the problème des ménages. Bull. Amer. Math. Soc., 49:784-785) diese una demostración.

A partir de aquí se han obtenido otras fórmulas, como la de Wyman & Moser de 1958(On the problème des ménages, Canadian Journal of Mathematics, 10 (3): 468–480, doi:10.4153/cjm-1958-045-6, MR 0095127).

En Non-sexist solution of the ménage problem, podéis encontrar la de Kenneth P. Bogart and Peter G. Doyle, que lo resuelve utilizando el principio de inclusión-exclusión.

Did you like this? Share it:
This entry was posted in Historia. Bookmark the permalink.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *