台面上的礼貌—夫妻围坐问题

按西方的礼仪，n 对夫妇围桌而坐，要求男女必须相邻而坐，而且一对夫妇不能相邻，也就是每位男士两边是两位女士但不能是他太太；每位女士两边是两位男士但不是她丈夫。按照这样的规则，问不同的入座数 Mn是多少？这个著名问题由卢卡斯在1891年提出来，在此之前，英国物理学家泰特研究纽结问题时出提出一个等价的问题，可见这个问题不是简单的数学游戏，许多数学家研究过这个问题。1934年，图夏尔给出Mn的一个具体表达式，但没有给出证明。最后美国著名数学家卡普兰斯基证明了这个公式。由此可见，这个问题是个不简单的问题。使许多数学家感到困难的是，由于“女士优先”（Ladiesfirst），也就是先把女士们的座位安排好，再把男士安排在其间，这样就形成有限制的排列问题，这问题要比原问题还难。卡普兰斯基的想法是打破这种礼貌上的限制，因为这对数学问题没什么必要，而直接考虑求解，从而轻易解决该问题。