В комбинаторной математике задача о мужчинах или проблема мужчин [1] требует количества различных способов, с помощью которых можно усадить группу пар мужчина-женщина за круглый обеденный стол, чтобы мужчины и женщины чередовались, и никто не садился рядом. своему партнеру. Эта проблема была сформулирована в 1891 году Эдуардом Лукасом и независимо, несколькими годами ранее, Питером Гатри Тэтом в связи с теорией узлов . [2] Для количества пар, равного 3, 4, 5, ... количество мест для сидения равно
Математики разработали формулы и рекуррентные уравнения для вычисления этих чисел и связанных последовательностей чисел. Наряду с их приложениями к этикету и теории узлов, эти числа также имеют теоретико-графовую интерпретацию: они подсчитывают количество паросочетаний и гамильтоновых циклов в определенных семействах графов.
Формула Тушара
Пусть M n обозначает количество посадочных мест для n пар. Тушар (1934) вывел формулу
Многие последующие работы были посвящены альтернативным доказательствам этой формулы и различным обобщенным версиям проблемы.
Другая Теневая формула для М н с участием полиномов Чебышева первого рода была дана Wyman & Moser (1958) .
Номера Ménage и решения, ориентированные на женщин
Есть 2 × n ! способы рассадки женщин: есть два набора сидений, которые можно расположить для женщин, и их n ! способы рассадки их на определенный набор сидений. Для каждой рассадки для женщин предусмотрены:
способы рассадки мужчин; эта формула просто опускает 2 × n ! коэффициент из формулы Тушара. Полученные меньшие числа (опять же, начиная с n = 3),
называются числами менажа . Факторэто число способов формирования K неперекрывающихся пар соседних мест или, что эквивалентно, число паросочетаний из K ребер в графе цикла из 2 п вершин. Выражение для A n является непосредственным результатом применения принципа включения-исключения к расположениям, в которых люди, сидящие на концах каждого края соответствия, должны быть парой.
До работы Bogart & Doyle (1986) решение проблемы с мужским составом принимало форму сначала нахождения всех расстановок для женщин, а затем подсчета для каждого из этих частичных расстановок сидений и количества способов их завершения, рассаживая женщин. мужчины подальше от своих партнеров. Богарт и Дойл утверждали, что формулу Тушара можно вывести напрямую, рассматривая все расстановки сидений сразу, а не исключая участие женщин. [3] Тем не менее, Kirousis & Kontogeorgiou (2018) нашли еще более прямолинейное решение, описанное выше, «дамы прежде всего», использовав несколько идей Богарта и Дойла (хотя они постарались переформулировать аргумент на негендерный язык).
Числа менажа удовлетворяют рекуррентному соотношению [4]
и более простое четырехчленное повторение [5]
из которых могут быть легко вычислены сами числовые показатели.
Теоретико-графические интерпретации
Решения проблемы менажа можно интерпретировать в терминах теории графов как направленные гамильтоновы циклы в графах короны . Граф короны формируется путем удаления идеального паросочетания из полного двудольного графа K n, n ; он имеет 2 n вершин двух цветов, и каждая вершина одного цвета соединена со всеми вершинами другого цвета, кроме одной. В случае задачи о мужчинах вершины графа представляют мужчин и женщин, а ребра представляют пары мужчин и женщин, которым разрешено сидеть рядом друг с другом. Этот граф формируется путем удаления идеального соответствия, образованного парами мужчина-женщина, из полного двудольного графа, который связывает каждого мужчины с каждой женщиной. Любое допустимое расположение сидячих мест можно описать последовательностью людей за столом, которая образует гамильтонов цикл на графике. Однако два гамильтоновых цикла считаются эквивалентными, если они соединяют одни и те же вершины в одном и том же циклическом порядке независимо от начальной вершины, тогда как в задаче о множестве стартовая позиция считается значимой: если, как в чаепитии Алисы , все гости меняют свое положение на одно место, это считается разным расположением сидений, даже если оно описывается одним и тем же циклом. Следовательно, количество ориентированных гамильтоновых циклов в графе короны меньше в 2 n раз, чем количество расстановок [6], но больше в ( n - 1) раз! чем количество людей. Последовательность номеров циклов в этих графах (как и раньше, начиная с n = 3) равна
Также возможно второе теоретико-графическое описание проблемы. После того, как женщины расселены, возможные расстановки для оставшихся мужчин можно описать как идеальные совпадения в графе, образованном удалением одного гамильтонова цикла из полного двудольного графа; у графа есть ребра, соединяющие открытые места с мужчинами, и удаление цикла соответствует запрету мужчинам сидеть на любом из открытых сидений рядом с их женами. Проблема подсчета паросочетаний в двудольном графе и, следовательно, a fortiori проблема вычисления чисел разносов, может быть решена с использованием перманентов некоторых матриц 0-1 . В случае задачи о доходах матрица, возникающая из этого взгляда на проблему, является циркулянтной матрицей, в которой все, кроме двух смежных элементов производящей строки, равны 1 . [7]
Теория узлов
Мотивация Тэта к изучению проблемы менажа возникла из попытки найти полный список математических узлов с заданным числом пересечений , скажем, n . В нотации Даукера для диаграмм узлов, ранняя форма которой использовалась Тэтом, 2 n точек, где узел пересекает сам себя, в последовательном порядке вдоль узла, помечены 2 n числами от 1 до 2 n . В сокращенной диаграмме две метки на перекрестке не могут быть последовательными, поэтому набор пар меток на каждом перекрестке, используемый в нотации Даукера для представления узла, можно интерпретировать как идеальное совпадение в графе, имеющем вершину для каждое число в диапазоне от 1 до 2 n и ребро между каждой парой чисел, которые имеют разную четность и не являются последовательными по модулю 2 n . Этот граф формируется путем удаления гамильтонова цикла (соединения последовательных чисел) из полного двудольного графа (соединяющего все пары чисел с разной четностью), и поэтому он имеет количество совпадений, равное количеству чисел. Для чередующихся узлов этого сопоставления достаточно, чтобы описать саму диаграмму узлов; для других узлов необходимо указать дополнительный положительный или отрицательный знак для каждой пары пересечения, чтобы определить, какая из двух нитей пересечения лежит над другой цепью.
Однако проблема перечисления узлов имеет некоторые дополнительные симметрии, отсутствующие в задаче о разводке: для одной и той же диаграммы узлов получаются разные нотации Даукера, если начинать разметку с другой точки пересечения, и все эти разные нотации следует рассматривать как представляющие одну и ту же диаграмму. диаграмма. По этой причине два сопоставления, которые отличаются друг от друга циклической перестановкой, должны рассматриваться как эквивалентные и учитываться только один раз. Гилберт (1956) решил эту модифицированную задачу перечисления, показав, что количество различных сопоставлений равно
Смотрите также
- Задача Обервольфаха , другая математическая задача, связанная с расстановкой посетителей за столами.
Заметки
- ^ «Ménage» - французское слово для «домашнего хозяйства» (здесь имеется в виду пара мужчина-женщина).
- ^ Dutka (1986) .
- ^ Gleick (1986) .
- ^ Мьюир (1882) ; Laisant (1891) . Более сложные рецидивы были описаны ранее Cayley и Muir (1878) .
- ^ Мьюир (1882) ; Кэнфилд и Вормальд (1987) .
- ^ Пассмор (2005) .
- ^ Мьюир (1878) ; Eades, Praeger & Seberry (1983) ; Кройтер (1984) ; Хендерсон (1975) .
Рекомендации
- Bogart, Kenneth P .; Дойл, Питер Г. (1986), "Non-сексистские решение проблемы MENAGE" , American Mathematical Monthly , 93 (7): 514-519, DOI : 10,2307 / 2323022 , JSTOR 2323022 , MR 0856291.
- Бонг, Нгуен-Хуу (1998), "числа Люка и проблема домочадцы", Международный журнал по математическому образованию в области науки и техники , 29 (5): 647-661, DOI : 10,1080 / 0020739980290502 , MR 1649926.
- Кэнфилд, Э. Родни; Вормальд, Николас К. (1987), «Числа Менажа, биекции и P-рекурсивность», Дискретная математика , 63 (2–3): 117–129, DOI : 10.1016 / 0012-365X (87) 90002-1 , MR 0885491.
- Дёрри, Генрих (1965), «Проблема Лукаса о супружеских парах», 100 Великих проблем элементарной математики , Довер, стр. 27–33, ISBN 978-0-486-61348-2. Перевод Дэвида Антина.
- Dutka Жак (1986), "О Probleme де ménages", Математическая Intelligencer , 8 (3): 18-33, DOI : 10.1007 / BF03025785 , MR 0846991.
- Идс, Питер ; Praeger, Cheryl E .; Себери, Дженнифер Р. (1983), "Некоторые замечания о перманентах циркулянтных (0,1) матриц", Utilitas Mathematica , 23 : 145–159, MR 0703136.
- Гилберт, Э. Н. (1956), "Узлы и классы перестановок групп", Scripta Mathematica , 22 : 228–233, MR 0090568.
- Глейк, Джеймс (28 октября 1986 г.), «Математика + сексизм: проблема» , New York Times.
- Хендерсон, JR (1975), "перманентах (0,1) -матрицы , имеющих не более двух нулей в строке", Канадский математический вестник , 18 (3): 353-358, DOI : 10,4153 / КМФ-1975-064-6 , MR 0399127.
- Холст, Ларс (1991), "О 'problème де ménages' с вероятностной точки зрения", Статистика и вероятность Letters , 11 (3): 225-231, DOI : 10.1016 / 0167-7152 (91) 90147-J , MR 1097978.
- Капланский, Ирвинг (1943), "Решение problème де ménages", Бюллетень Американского математического общества , 49 (10): 784-785, DOI : 10,1090 / S0002-9904-1943-08035-4 , MR 0009006.
- Каплански, Ирвинг ; Риордан, Дж. (1946), «Проблема людей», Scripta Mathematica , 12 : 113–124, MR 0019074..
- Kirousis, L .; Контогеоргиу, Г. (2018), «102.18. Повторное посещение проблемы мужчин », The Mathematical Gazette , 102 (553): 147–149, arXiv : 1607.04115 , doi : 10.1017 / mag.2018.27.
- Kräuter, Арнольд Ричард (1984), "Uber die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen" , Séminaire Lotharingien de Combinatoire (на немецком языке), B11b.
- Laisant, Charles-Ange (1891), «Sur deux problèmes de permutations» , Vie de la société, Bulletin de la Société Mathématique de France (на французском языке), 19 : 105–108.
- Лукас, Эдуард (1891), Теория Номбр , Париж: Готье-Виллар, стр. 491–495.
- Мьюир, Томас (1878), "О проблеме расположения профессора Тейта", Труды Королевского общества Эдинбурга , 9 : 382–391. Включает (стр. 388–391) дополнение Артура Кэли .
- Мьюир, Томас (1882 г.), «Дополнительное примечание к проблеме размещения», Труды Королевского общества Эдинбурга , 11 : 187–190.
- Пассмор, Аманда Ф. (2005), Элементарное решение проблемы найма , CiteSeerX 10.1.1.96.8324.
- Риордан, Джон (1952), "Арифметика чисел Menage", Герцог математический журнал , 19 (1): 27-30, DOI : 10,1215 / S0012-7094-52-01904-2 , МР 0045680.
- Такач, Лайош (1981), «О« проблеме отношений » », Дискретная математика , 36 (3): 289–297, DOI : 10.1016 / S0012-365X (81) 80024-6 , MR 0675360.
- Touchard, J. (1934), "Sur un problème de permutations" , CR Acad. Sci. Париж , 198 (631–633).
- Вайман, Макс; Moser, Лео (1958), "О problème де ménages", Canadian Journal математики , 10 (3): 468-480, DOI : 10,4153 / CJM-1958-045-6 , МР 0095127.
Внешние ссылки
- Вайсштейн, Эрик В. "Проблема супружеских пар" . MathWorld .
- Вайсштейн, Эрик В. "Формула повторения Лайзанта" . MathWorld .