0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Представим, что вы организуете круглый стол, и вам важно, в каком порядке будут рассажены участники. В комбинаторике такую задачу называют "задачей о супружеских парах" или методом Le Problème des Ménages.</p>
1
<p>Представим, что вы организуете круглый стол, и вам важно, в каком порядке будут рассажены участники. В комбинаторике такую задачу называют "задачей о супружеских парах" или методом Le Problème des Ménages.</p>
2
<p>В этом уроке разберем, как работает такой метод.</p>
2
<p>В этом уроке разберем, как работает такой метод.</p>
3
<h3>Решаем задачу о супружеских парах</h3>
3
<h3>Решаем задачу о супружеских парах</h3>
4
<p>Для начала рассмотрим самую распространенную формулировку этой задачи:</p>
4
<p>Для начала рассмотрим самую распространенную формулировку этой задачи:</p>
5
<p>Допустим, у нас есть n пар, каждая из которых состоит из мужчины и женщины.</p>
5
<p>Допустим, у нас есть n пар, каждая из которых состоит из мужчины и женщины.</p>
6
<p>Их нужно рассадить за круглым столом так, чтобы мужчины и женщины чередовались. При этом женщины должны сидеть на нечетных местах и ни одна из них не может сидеть рядом со своим партнером.</p>
6
<p>Их нужно рассадить за круглым столом так, чтобы мужчины и женщины чередовались. При этом женщины должны сидеть на нечетных местах и ни одна из них не может сидеть рядом со своим партнером.</p>
7
<p>Нужно вычислить, сколько существует вариантов рассадки.</p>
7
<p>Нужно вычислить, сколько существует вариантов рассадки.</p>
8
<p>Чтобы решить эту задачу, используем принцип включения и исключения.</p>
8
<p>Чтобы решить эту задачу, используем принцип включения и исключения.</p>
9
<p>Для начала переведем задачу на язык математики и присвоим имена:</p>
9
<p>Для начала переведем задачу на язык математики и присвоим имена:</p>
10
<ul><li>Пусть 1, . . . , n - множество пар</li>
10
<ul><li>Пусть 1, . . . , n - множество пар</li>
11
<li>При этом A - множество рассадок, в которых женщины занимают нечетные места</li>
11
<li>При этом A - множество рассадок, в которых женщины занимают нечетные места</li>
12
<li>Нужно найти те члены в A, для которых ни одна пара не сидит вместе</li>
12
<li>Нужно найти те члены в A, для которых ни одна пара не сидит вместе</li>
13
<li>Выражение V subseteq n обозначим через множество расстановок AV</li>
13
<li>Выражение V subseteq n обозначим через множество расстановок AV</li>
14
<li>Множество AV обозначает пары из множества V, которые нарушают правило</li>
14
<li>Множество AV обозначает пары из множества V, которые нарушают правило</li>
15
<li>По симметрии размер |AV | зависит от размера V, а не от конкретного выбора пар</li>
15
<li>По симметрии размер |AV | зависит от размера V, а не от конкретного выбора пар</li>
16
<li>Поэтому сделаем такой вывод - если |V| = k, обозначим ak := |AV |</li>
16
<li>Поэтому сделаем такой вывод - если |V| = k, обозначим ak := |AV |</li>
17
</ul><p>Далее находим нужное число. Для этого применим принцип включения и исключения:</p>
17
</ul><p>Далее находим нужное число. Для этого применим принцип включения и исключения:</p>
18
<p>sumnk=0(-1)k(nk)=0</p>
18
<p>sumnk=0(-1)k(nk)=0</p>
19
<p>Далее введем обозначение bk - это количество способов, с помощью которых можно выбрать k пар стульев, расположенных рядом друг с другом.</p>
19
<p>Далее введем обозначение bk - это количество способов, с помощью которых можно выбрать k пар стульев, расположенных рядом друг с другом.</p>
20
<p>Наши k плохих пар могут располагаться над плохими парами мест k! способами. Поэтому мы приходим к такому выражению:</p>
20
<p>Наши k плохих пар могут располагаться над плохими парами мест k! способами. Поэтому мы приходим к такому выражению:</p>
21
<p>ak = b_kk!(n-k)!(n-k)!</p>
21
<p>ak = b_kk!(n-k)!(n-k)!</p>
22
<p>После этого мы можем рассадить оставшихся женщин (n - k)! способами, а оставшихся мужчин - (n - k)! способами.</p>
22
<p>После этого мы можем рассадить оставшихся женщин (n - k)! способами, а оставшихся мужчин - (n - k)! способами.</p>
23
<p>Вот так может выглядеть схема рассадки:</p>
23
<p>Вот так может выглядеть схема рассадки:</p>
24
<p>Здесь три пары сидят вместе, что не соответствует первоначальному условию рассадки.</p>
24
<p>Здесь три пары сидят вместе, что не соответствует первоначальному условию рассадки.</p>
25
<p>Остается определить bk. Для этого разорвем окружность в фиксированной точке. Далее сотрем буквы в кругах, так как они фиксированы. Также стираем круги внутри прямоугольников, так как их количество известно - по два круга в каждом прямоугольнике.</p>
25
<p>Остается определить bk. Для этого разорвем окружность в фиксированной точке. Далее сотрем буквы в кругах, так как они фиксированы. Также стираем круги внутри прямоугольников, так как их количество известно - по два круга в каждом прямоугольнике.</p>
26
<p>В итоге получим такой рисунок:</p>
26
<p>В итоге получим такой рисунок:</p>
27
<p>В процессе решения задачи мы пришли к такой формуле:</p>
27
<p>В процессе решения задачи мы пришли к такой формуле:</p>
28
<p>b^k=(2n-k)/k + (2n-k-1)/(k-1) = (2n-k)/k + k/(2n-k)times(2n-k)/k = 2n/(2n-k)times(2n-k)/k</p>
28
<p>b^k=(2n-k)/k + (2n-k-1)/(k-1) = (2n-k)/k + k/(2n-k)times(2n-k)/k = 2n/(2n-k)times(2n-k)/k</p>
29
<p>Комбинируем приведенные формулы, немного упрощаем и получаем решение:</p>
29
<p>Комбинируем приведенные формулы, немного упрощаем и получаем решение:</p>
30
<p>n!sum_{k=0}^{n}(2n)/(2n-k)times(2n-k)/ktimes(n-k)!(-1)^k</p>
30
<p>n!sum_{k=0}^{n}(2n)/(2n-k)times(2n-k)/ktimes(n-k)!(-1)^k</p>
31
<h3>Выводы</h3>
31
<h3>Выводы</h3>
32
<p>Теперь вы знаете, как решать задачи типа "супружеских пар". С помощью этого метода можно вычислить количество вариантов расположения элементов по условиям, которые мы задали.</p>
32
<p>Теперь вы знаете, как решать задачи типа "супружеских пар". С помощью этого метода можно вычислить количество вариантов расположения элементов по условиям, которые мы задали.</p>
33
<p>Особенность такого метода заключается в том, что для решения можно использовать принцип включения и исключения, который мы изучили ранее.</p>
33
<p>Особенность такого метода заключается в том, что для решения можно использовать принцип включения и исключения, который мы изучили ранее.</p>