problème des convives

problème des ménages

COMBINATOIRE

Problème de combinatoire, il s’agit de dénombrer les différentes façons de placer un nombre donné de couples autour d’une table de façon à alterner hommes et femmes et à ne placer personne à côté de son (ou sa) conjoint(e).

Ce problème a été formulé indépendamment par Édouard Lucas et indépendamment par Peter Guthrie Tait .
Des relations de récurrence permettent de calculer le nombre de placements suivant le nombre de convives. Ce problème est en relation avec la théorie des nœuds et peut être interprété en théorie des graphes.