Проблема управления
Задача о назначениях в комбинаторной математике
Стол на десять персон. Существует 3120 различных способов, которыми пять пар мужчина-женщина могут сесть за этот стол, так что мужчины и женщины чередуются, и никто не садится рядом со своим партнером.

В комбинаторной математике задача о менажах или problème des ménages заключается в определении количества различных способов рассадки мужчин и женщин за круглым обеденным столом так, чтобы мужчины и женщины сидели попеременно, и никто не сидел рядом со своим партнером. ( Ménage — французское слово, означающее «домохозяйство», в данном случае относится к паре мужчина-женщина.) Эта задача была сформулирована в 1891 году Эдуардом Люка и, независимо от него, несколькими годами ранее Питером Гатри Тейтом в связи с теорией узлов . [1] Для числа пар, равного 3, 4, 5, ..., количество вариантов рассадки равно

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (последовательность A059375 в OEIS ).

Математики разработали формулы и рекуррентные уравнения для вычисления этих чисел и связанных последовательностей чисел. Наряду с их приложениями к этикету и теории узлов, эти числа также имеют теоретико-графическую интерпретацию: они подсчитывают количество паросочетаний и гамильтоновых циклов в определенных семействах графов .

Формула Тушара

Пусть M n обозначает число мест для n пар. Тушар (1934) вывел формулу

М н = 2 ⋅ н ! ∑ к = 0 н ( − 1 ) к 2 н 2 н − к ( 2 н − к к ) ( н − к ) ! . {\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!.}

Значительная часть последующей работы была направлена ​​на альтернативные доказательства этой формулы и на различные обобщенные версии проблемы.

Другая общая формула для M n , включающая полиномы Чебышева первого рода, была предложена Вайманом и Мозером (1958).

Цифры Ménage и решения для женщин

Существует 2× n ! способов рассадки женщин: есть два набора сидений, которые могут быть организованы для женщин, и есть n ! способов рассадить их на определенный набор сидений. Для каждого расположения сидений для женщин есть

А н = ∑ к = 0 н ( − 1 ) к 2 н 2 н − к ( 2 н − к к ) ( н − к ) ! {\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(nk)!}

способы рассадки мужчин; эта формула просто опускает множитель 2× n ! из формулы Тушара. Получающиеся меньшие числа (опять же, начиная с n  = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (последовательность A000179 в OEIS )

называются числами ménage . Фактор — это число способов формирования k неперекрывающихся пар соседних мест или, что то же самое, число совпадений k ребер в циклическом графе из 2 n вершин . Выражение для A n является непосредственным результатом применения принципа включения-исключения к расположениям, в которых люди, сидящие в конечных точках каждого ребра совпадения, должны быть парой. 2 н 2 н − к ( 2 н − к к ) {\displaystyle {\frac {2n}{2n-k}}{2n-k \выберите k}}

До работы Богарта и Дойла (1986) решения проблемы управления принимали форму сначала поиска всех вариантов рассадки для женщин, а затем подсчета для каждого из этих частичных вариантов рассадки количества способов завершить его, посадив мужчин подальше от их партнеров. Богарт и Дойл утверждали, что формулу Тушара можно вывести напрямую, рассматривая все варианты рассадки сразу, а не вынося за скобки участие женщин. [2] Однако Кирусис и Контогеоргиу (2018) нашли еще более простое решение с дамами первыми, описанное выше, используя несколько идей Богарта и Дойла (хотя они постарались переформулировать аргумент в негендерный язык).

Числа хозяйства удовлетворяют рекуррентному соотношению [3]

А н = н А н − 1 + н н − 2 А н − 2 + 4 ( − 1 ) н − 1 н − 2 {\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}

и более простая четырехчленная рекуррентность [4]

А н = н А н − 1 + 2 А н − 2 − ( н − 4 ) А н − 3 − А н − 4 , {\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4},}

из чего можно легко рассчитать сами цифры хозяйства.

Графо-теоретические интерпретации

Графы корон с шестью, восемью и десятью вершинами. Внешний цикл каждого графа образует гамильтонов цикл; графы с восемью и десятью вершинами также имеют другие гамильтоновы циклы.

Решения проблемы управления могут быть интерпретированы в терминах теории графов как направленные гамильтоновы циклы в графах корон . Граф короны образуется путем удаления идеального паросочетания из полного двудольного графа K n,n ; он имеет 2 n вершин двух цветов, и каждая вершина одного цвета соединена со всеми вершинами другого цвета, кроме одной. В случае проблемы управления вершины графа представляют мужчин и женщин, а ребра представляют пары мужчин и женщин, которым разрешено сидеть рядом друг с другом. Этот граф образуется путем удаления идеального паросочетания, образованного парами мужчина-женщина, из полного двудольного графа, который соединяет каждого мужчину с каждой женщиной. Любое допустимое расположение мест можно описать последовательностью людей по порядку вокруг стола, что образует гамильтонов цикл в графе. Однако два гамильтоновых цикла считаются эквивалентными, если они соединяют одни и те же вершины в одном и том же циклическом порядке независимо от начальной вершины, в то время как в задаче о менажах начальная позиция считается значимой: если, как на чаепитии Алисы , все гости меняют свои позиции на одно место, это считается другой рассадкой, даже если она описывается тем же циклом. Таким образом, число ориентированных гамильтоновых циклов в графе короны меньше в 2 n раз , чем число рассадок, [5] но больше в ( n − 1) раз  !, чем числа менажей. Последовательность чисел циклов в этих графах (как и прежде, начиная с n  = 3) равна

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (последовательность A094047 в OEIS ).

Второе графо-теоретическое описание проблемы также возможно. После того, как женщины рассажены, возможные рассадки для оставшихся мужчин можно описать как идеальные соответствия в графе, образованном путем удаления одного гамильтонова цикла из полного двудольного графа; граф имеет ребра, соединяющие открытые места с мужчинами, и удаление цикла соответствует запрету мужчинам сидеть на любом из открытых мест, смежных с их женами. Проблема подсчета соответствий в двудольном графе , и, следовательно, a fortiori проблема вычисления чисел менаж, могут быть решены с использованием перманентов определенных матриц 0-1 . В случае проблемы менаж матрица, возникающая из этого взгляда на проблему, является циркулянтной матрицей, в которой все, кроме двух смежных элементов порождающей строки, равны 1. [6]

Теория узлов

Мотивация Тейта к изучению проблемы управления возникла из-за попытки найти полный список математических узлов с заданным числом пересечений , скажем, n . В нотации Даукера для диаграмм узлов, ранняя форма которой использовалась Тейтом, 2 n точек, где узел пересекает сам себя, в последовательном порядке вдоль узла, помечены 2 n числами от 1 до 2 n . В сокращенной диаграмме две метки на пересечении не могут быть последовательными, поэтому набор пар меток на каждом пересечении, используемый в нотации Даукера для представления узла, можно интерпретировать как идеальное соответствие в графе, который имеет вершину для каждого числа в диапазоне от 1 до 2 n и ребро между каждой парой чисел, которые имеют различную четность и не являются последовательными по модулю 2 n . Этот граф образован путем удаления гамильтонова цикла (соединяющего последовательные числа) из полного двудольного графа (соединяющего все пары чисел с разной четностью), и поэтому он имеет число сопоставлений, равное числу менаж. Для чередующихся узлов этого сопоставления достаточно для описания самой диаграммы узла; для других узлов необходимо указать дополнительный положительный или отрицательный знак для каждой пары пересечений, чтобы определить, какая из двух нитей пересечения лежит над другой нитью.

Однако проблема перечисления узлов имеет некоторые дополнительные симметрии, отсутствующие в проблеме управления: мы получаем разные обозначения Доукера для одной и той же диаграммы узлов, если начинаем маркировку с другой точки пересечения, и все эти разные обозначения следует считать представляющими одну и ту же диаграмму. По этой причине два сопоставления, которые отличаются друг от друга циклической перестановкой, следует рассматривать как эквивалентные и учитывать только один раз. Гилберт (1956) решил эту модифицированную задачу перечисления, показав, что число различных сопоставлений равно

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (последовательность A002484 в OEIS ).

Смотрите также

  • Задача Обервольфаха — другая математическая задача, связанная с рассадкой обедающих за столами.
  • Problème des rencontres , аналогичная проблема, связанная с частичными расстройствами.

Примечания

  1. ^ Дутка (1986).
  2. ^ Глейк (1986).
  3. ^ Muir (1882); Laisant (1891). Более сложные рецидивы были описаны ранее Cayley и Muir (1878).
  4. ^ Мьюир (1882); Кэнфилд и Вормолд (1987).
  5. ^ Пассмор (2005).
  6. ^ Мьюир (1878); Идс, Прегер и Себерри (1983); Кройтер (1984); Хендерсон (1975).

Ссылки

  • Богарт, Кеннет П.; Дойл, Питер Г. (1986), «Несексистское решение проблемы ménage», 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. Перевод Дэвида Энтина.
  • Дутка, Жак (1986), «О проблеме управления», The Mathematical Intelligencer , 8 (3): 18–33 , doi : 10.1007/BF03025785, MR  0846991, S2CID  116433056.
  • Идс, Питер ; Прегер, Шерил Э .; Себерри, Дженнифер Р. (1983), «Некоторые замечания о перманентах циркулянтных (0,1) матриц», Utilitas Mathematica , 23 : 145–159 , MR  0703136.
  • Гилберт, EN (1956), «Узлы и классы перестановок в хозяйстве», Scripta Mathematica , 22 : 228–233 , MR  0090568.
  • Глейк, Джеймс (28 октября 1986 г.), «Математика + сексизм: проблема», New York Times.
  • Хендерсон, Дж. Р. (1975), «Перманенты (0,1)-матриц, имеющие не более двух нулей в строке», Канадский математический вестник , 18 (3): 353–358 , doi : 10.4153/CMB-1975-064-6 , MR  0399127.
  • Холст, Ларс (1991), «О «проблеме управления» с вероятностной точки зрения», Statistics and Probability Letters , 11 (3): 225– 231, doi :10.1016/0167-7152(91)90147-J, MR  1097978.
  • Капланский, Ирвинг (1943), «Решение проблемы управления», Бюллетень Американского математического общества , 49 (10): 784– 785, doi : 10.1090/S0002-9904-1943-08035-4 , MR  0009006.
  • Каплански, Ирвинг ; Риордан, Дж. (1946), «Проблема управления», Scripta Mathematica , 12 : 113–124 , MR  0019074..
  • Кирусис, Л.; Контогеоргиу, Г. (2018), «102.18 Возвращение к проблеме управления », The Mathematical Gazette , 102 (553): 147–149 , arXiv : 1607.04115 , doi : 10.1017/mag.2018.27, S2CID  126036427.
  • Кроутер, Арнольд Рихард (1984), «Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen», Séminaire Lotharingien de Combinatoire (на немецком языке), B11b.
  • Лесан, Шарль-Анж (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 , doi :10.1017/S0370164600032557. Включает (стр. 388–391) дополнение Артура Кейли .
  • Мьюир, Томас ( 1882 ), «Дополнительное примечание по проблеме расположения», Труды Королевского общества Эдинбурга , 11 : 187–190.
  • Пассмор, Аманда Ф. (2005), Элементарное решение проблемы ведения хозяйства , CiteSeerX  10.1.1.96.8324.
  • Риордан, Джон (1952), «Арифметика чисел в хозяйстве», Duke Mathematical Journal , 19 (1): 27– 30, doi :10.1215/S0012-7094-52-01904-2, MR  0045680.
  • Такач, Лайош (1981), «О «проблеме управления»", Дискретная математика , 36 (3): 289– 297, doi :10.1016/S0012-365X(81)80024-6, MR  0675360.
  • Тушар, Дж. (1934), «Sur un problème de permutations», CR Acad. наук. Париж , 198 ( 631–633 )..
  • Вайман, Макс; Мозер, Лео (1958), «О проблеме управления», Canadian Journal of Mathematics , 10 (3): 468–480 , doi : 10.4153/cjm-1958-045-6 , MR  0095127.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ménage_problem&oldid=1170975197"