В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 4
Текст из файла (страница 4)
Задачу о числе беспорядков называют также задачей Монмора.Другой известной задачей на перестановки с ограничениями является задача Люка, или задача о супружескихпарах. Она заключается в нахождении числа рассадок за круглый 2n-местный стол n супружеских пар так, чтобы никакая супружеская пара не оказалась на соседних стульях. Иногда эту задачу называют также задачей мажордома.Пусть все стулья пронумерованы символами 1, 10 , 2, 20 , . . .
, n, n0 . Будем без ограничения общности рассуждений считать, что на стульях со штрихами могут сидеть персоны лишь одного пола. Для начала заметим, что перед тем, какбудут рассажены все пары, можно рассмотреть всевозможные рассадки дам и относительно уже их искать допустимые рассадки мужчин. Таким образом, число разрешенных рассадок супружеских пар равно 2 · n! ·Un , где Un — числоспособов рассадить n мужчин так, чтобы супруги не сидели рядом. Таблица запретов будет в данном случае выглядетьследующим образом:1 2 ...i...
n−1 n1 2 ...i... n−1 n2 3 ... i+1 ...n1(1.7)p1 p2 . . .pi. . . pn−1 pnp01 p02 . . .p0i. . . p0n−1 p0nЗадача сводится к вычислению перманента матрицы0 01 01 11 1. . . .1 10 11001...111100..11......................1111..011111. .00Если обозначить через J матрицу, все элементы которой суть единицы, I — единичную (на диагонали которой стоятединицы, а вне диагонали нули), C — циркулярную матрицу, у которой над диагональю, а также на месте элемента первого столбца последней строки стоят единицы, а остальные элементы равны нулю, то задача Люка сводится квычислению per (J − I −C), а задача Монмора к per (J − I).Введем 2n вообще говоря противоречивых свойств, причем противоречивыми являются любые наборы, содержащие хотя бы одну из пар p1 , p01 , p01 , p2 , p2 , p02 , p02 , p3 , . .
. , pi , p0i , p0i , pi+1 , . . . , p0n−1 , pn , pn , p0n , p0n , p1 .Это легко представить на рисунке, расположив эти свойства в круг:p1p0np01HpnAAp2AAp02······Hp0ipi(1.8)Из этих 2n объектов, расположенных в круге, выбирается k, не расположенных рядом. Решим сначала вспомогательную задачу: найдем число способов выбрать из n расположенных в ряд объектов k, не расположенных рядом.Лемма 1.1.1 (Капланский).n−k+1ne ∈ B | ∀ i = 1, n − 1 =⇒ αi αi+1 = 0 =f (n, k) = ] α.k Док-во.
Очевидно, что f (1, 0) = f (1, 1) = 1, k > 2 ⇒ f (1, k) = 0. Докажем по индукции следующее предложение:f (n, k) = f (n − 1, k) + f (n − 2, k − 1)(1.9)111.1. ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛАДействительно, способы выбрать k несоседствующих объектов распадаются на два непересекающихся варианта: последний элемент не выбран, но тогда число способов выбрать k объектов среди n − 1 первых равно как раз f (n − 1, k);последний элемент выбран, в этом случае выбирать k − 1 объектов можно только среди первых n − 2, то есть число способов f (n − 2, k − 1).
Предложение доказано. Для полного определения f (n, k) осталось определить вторую строчку ипервые два столбца:f (2, 0) = 1, f (2, 1) = 2, k > 3 ⇒ f (2, k) = 0, f (n, 0) = 1, f (n, 1) = n.Наглядно это можно представить на таблице:b kn b012345601111111101234562 30 00 00 0. 0. . .........4 5...0 0...0 0...0 0...............0 ...................................n−2,k−1.........(1.10)n−1,kn,kТеперь легко понять, что решением такого рекуррентного уравнения будет являться как раз требуемый биномиальныйкоэффициент n−k+1.kЛемма 1.1.2 (Капланский).e ∈ Bn | ∀ i = 1, n − 1 =⇒ αi αi+1 = 0, α1 αn = 0 =g (n, k) = ] αnn−k.n−kk Док-во.
При выборе k объектов из цикла (1.8) возможны два случая: последний объект не выбран — в этом случаечисло вариантов просто равно f (n − 1, k); последний объект выбран — тогда число вариантов f (n − 3, k − 1), так какпомимо последнего нельзя выбирать также теперь предпоследний и первый. Таким образом,g (n, k) = f (n − 1, k) + f (n − 3, k − 1) = nn−kn−kn−k−1n−kk=, (1.11)+=1+n−kn−kkkk−1kчто и требовалось доказатьТеперь мы готовы дать ответ на вопрос задачи Люка: Mn = 2n!Un , где Un — число перестановок с ограничениями,входящими в противоречиедруг с другом в соответствии с (1.8). Число выбрать из 2n свойств k непротиворечивых2n 2n−k.Тогдалегко видеть, что согласно принципу включения и исключенияравно vk = 2n−kkUn = v0 · n! − v1 · (n − 1)! + v2 · (n − 2)! − · · · + (−1)k vk · (n − k)! + · · · + (−1)n vn · (n − n)! =n2n2n − k∑ (−1) 2n − k k (n − k)!.k=0kПримеры.1.
Имеется колода из 4n (n > 5) карт, которая содержит карты четырех мастей по n карт каждой масти, занумерованных числами 1, 2, . . . , n. Подсчитать, сколькими способами можно выбрать пять карт так, что среди них окажутся:(a) Пять последовательных карт одной масти. Решение. Если представить колоду в виде таблицы 4 × n, строки которой будут содержать карты одноймасти, упорядоченные по возрастанию, то легко увидеть, что число искомых способов равно 4 (n − 4).nДействительно, одним из 4 способов можно выбрать одну строку, а затем одним из n − 4 способов — последовательность из 5 подряд идущих карт.12ГЛАВА 1. КОМБИНАТОРИКА(b) Пять последовательных карт, из которых по крайней мере две разных мастей. Решение.
Снова обращаясь к таблице, можно понять, что всего подряд идущих пятерок 45 (n − 4), изкоторых согласно (1a) 4 (n − 4) состоят из карт одной масти. Следовательно, неоднородных пятерок всего45 (n − 4) − 4 (n − 4) = 1020 (n − 4).(c) Четыре карты из пяти с одинаковыми номерами. Решение.
Снова из таблицы видно, что такому выбору соответствует выбор целого столбца таблицы(n способов) и выбор еще одной карты среди оставшихся n − 1 столбцов, то есть всего возможностейn (4n − 4) = 4n (n − 1).(d) Три карты с одним номером и две карты с другими. Решение.
Такой выбор равносиленвыделению в таблице одного столбца (n способов), в котором затемвыбираются 3 элемента ( 43 способов), после чего выбираются два других столбца ( n−12 ), в каждом из4которых выбирается по 1 элементу ( 1 способов независимо для каждого столбца). Таким образом, всего 42n · 43 · n−12 · 1 = 32n (n − 1) (n − 2) способов.2.
Найти число способов раскладки n различных шаров по m различным урнам. Решение. Это число, очевидно, равно найденному в параграфе 1.1 числу различных отображений nэлементного множества в m-элементное, то есть mn .3. Сколькими способами можно разместить n одинаковых шаров по m различным урнам? Решение. Это число является числом решений системы (1.1), то есть числу сочетаний с повторениямиn+m−1.n4. Сколькими способами можно разложить n = n1 + n2 + · · · + nk различных шаров по k различным урнам так, чтобыв первую урну попало n1 шаров, во вторую — n2 и так далее, в k-ю — nk ? Решение.
Это число вычисляется непосредственно: сначала из n шаров выбираем n1 шаров ( nn1 способами)1 способами) и помеи помещаем их в первую урну. Затем из оставшихся n − n1 шаров выбираем n2 шаров ( n−nn2щаем их во вторуюурну и так далее, из оставшихся невыбранными n − n1 − · · · − nk−1 шаровnk шаров n−n выбираем1 · · · n−n1 −···−nk−1 =k−1 = 1 способами) и помещаем их в k-ю урну. Всего способов получается n( n−n1 −···−nnkn1n2 nknn!n1 !n2 !···nk ! . Это число называется полиномиальным коэффициентом и обозначается n1 n2 ···nk . По аналогии с биnномиальными коэффициентами, являющимися коэффициентами разложения бинома Ньютона (1 + x)n = ∑ nk xknnили, что то же самое, (a + b) = ∑k=0жения аналогичного полинома:k=0n k n−k, полиномиальные коэффициенты являются коэффициентами разлоk a b(a1 + a2 + · · · + ak )n =∑n1 +n2 +···+nk =nni >0, i=1,knan11 an22 · · · ak k .5.
n (n > 2) человек садятся за круглый стол. Два размещения по местам будем считать совпадающими, если каждыйчеловек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол? Решение. Каждой рассадке взаимно однозначно соответствует перестановка n целых чисел 0, 1, .
. . , n − 1. Всеn! перестановок разбиваются на классы эквивалентности по следующему принципу: две перестановки π1 и π2эквивалентны в том и только в том случае, когда либо π1 (x) = π2 (x + i) для некоторого i ∈ {0, . . . , n − 1} (сложениепроизводится по модулю n) и для всех x = 1, n, либо π1 (x) = π2 (i − x) для некоторого i ∈ {0, . . . , n − 1} (вычитаниепроизводится по модулю n) и для всех x = 1, n.
В каждом классе эквивалентности 2n перестановок, n сдвигов и nn!отраженных сдвигов. Таким образом, всего классов эквивалентности 2n= (n−1)!= [n − 1]n−2 .26. Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одногопола не сидели рядом?131.1. ПРОСТЕЙШИЕ КОМБИНАТОРНЫЕ ЧИСЛА Решение. Будем обозначать множество женщин числами 1, . . . , n, а множество мужчин — числами n+1, .
. . , 2n.Каждая рассадка являются перестановкой объединения этих множеств. Перестановка, соответствующая рассадке, удовлетворяющей условию, должна числа 1, . . . , n сопоставлять либо только четным числам, либо нечетным (2 возможности), при этом автоматически числа n + 1, . . . , 2n сопоставятся только нечетным, либо толькочетным числам. Переставить первые n чисел указанным образом можно n! способами, при этом для каждой ихперестановки вторые n чисел можно переставить также n! способами. Таким образом, всего искомых перестановок 2 (n!)2 .7. Сколькими способами можно составить три пары из n шахматистов?n−4 Решение. Первую пару можно выбрать n2 способами, вторую n−22 , третью2 .
При этом порядок пар неимеет значения. Одну и ту же тройку пар можно упорядочить 3! способами, то есть всего способов составить три [n](n)(n−2)(n−4)пары 2 23! 2 = 15 n6 = 486 .8. Сколько делителей имеет число q = pα1 1 pα2 2 · · · pαn n , где pi — различные простые числа, αi — некоторые натуральные числа? Чему равна сумма делителей? Решение. Очевидно, что число r является делителем числа q в том и только в том случае, когда q =np1 1 p2 2 · · · pn n , βi 6 αi .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
