Введение в прикладную комбинаторику, Кофман А. (984071), страница 19
Текст из файла (страница 19)
Пусть (20.10) выполняется для всех множеств с числом объектов, меньшим и: 1(п — 1, й)=С -ь ((и — 2, й — !)=С -ь (20.16) Тогда 1 (и — 1, й) + 1 (и — 2, й — 1) = С„ь -1- С~:,~ = (п — ь)! (и — ч)! и+! й((п — хь)! + (ь — !)((п — хь-) !)( — — С"-ь.ь' й~( з, (20.17) й) = п й С„ы й(~ 2 . (20,18) !3! и (20.!О) доказано. В т о р а я л е м м а. Пусть из и различимых объектов, расположенных на окружности, выбираются й объектов. Тогда число д(п, й) таких наборов, что никакие два из выбранных объектов не являются последовательными, равно Например, при и=7 и (с =3 (рис.
4!) ьг (7, 3) 4 Сг = — ° 4 = 7 . (20.19) Эти наборы АСЕ, АСЕ, АЭГ, ВЕ)Е, ВВС, ВЕС, СЕВ. Как и раньше, разобьем множество наборов на два подмножества: наборы, содержащие первый объект, и наборы, не содержащие его. Так как число наборов первого подмножества равно 7(п — 3, й — 1), 7" (и — 1, )г), (20.20) а второго (20.21) то 1, )г)+7(п — 3, lг — 1)=С -г+С -х-:= (и — й — !)! и (и — )г) ! (г) — ))! (и — 2)г)! и — )г ()г — ))! (и — 2и)! д(и, )г) = ! (ив (и — гг)! )г! (и — 2)г)! , С -ы )г(~ 2, (20.22) и (20.!8) доказано.
Рассмотрим теперь перестановки элементов 1, 2, ..., п. Обозначим через У, свойство: в перестановке объект г стоит на г-м А месте; через У; — свойство; в перестановке объект г стоит на (г + 1)-м месте Ьг ° (г=!, 2, ..., п — !), и через У„'— свойство: объект п стоит на первом месте. й" ° Рассмотрим эти 2п свойств в следующем порядке: У„У',, У, У.;, ..., У,, У„'. (20.23) Е Фиксируем )г из них, с1исло перестановок, Рис.
4!. удовлетворяющих этим свойствам, равно (и — )г)1, если свойства не противоречивы, и нулю в:противном случае. Если обозначим через ои число наборов нз й непротиворечивых свойств, а через (7 — число перестановок, не удовлетворяющих ни одному из свойств (20.23), то по формуле решета (12.20) с ыи —— ох (и — )г) ! (20.24) имеем ()и= ос. и! — о,. (п — 1)!+ ох (и — 2)! — ... + ( — 1)" ол О!, (20.25) !32 Применяя теперь вторую лемму Капланского к множеству (20.23), получаем (20.26) Подставляя (20.26) в (20.25), находим и„=и1 —,„, Се., (и-1)!+,„, С'.=„з ( -2)1 — ... 2п 2п + ( 1) „Сп 01, и ) 1.
(20.27) У П Р А )К Н Е Н И Я 20А, По формулам 120.2) и 120.3) вычислить Мм 20В. То же самое по формуле Тупара. 20В. Пусть пз 9 различимых обьектов на прямой выбираются 5 объектов. Каково число таких наборов, что никакие два объекта в ннх пе являготся соседними. 20Г. То же самое для 13 объектов, расположенных на окружности, и наборов пз 7 объектов. 20Д.
Тот же вопрос, что и в упражнении 20Г, но: а) двз фиксированных объекта должны содержаться в каждом наборе, б] два фиксированных объекта ие содержатся в одном и том же наборе. В 21. Перестановки с запретными положениями. размещение по ячейкам Задача о встречах и задача о супружеских парах — частные случаи задач, описываемых булевыми матрицами с ограничениями на расположение единиц (рис. 37 и 38).
Эти две задачи можно решать с помощью перманента соответствующих булевых матриц, но процесс его вычисления в большинстве случаев неэффективен. Поэтому попытаемся применить к задачам такого рода метод производящих функций. Булеву матрицу можно рассматривать в некотором смысле как шахматную доску. Заштрихованным клеткам в булевой матрице соответствуют нули, а незаштрихованным — единицы.
Будем булеву матрицу называть также «сотами» *), так как в различных задачах требуется размещать объекты по ячейкам, объединенным в <ссоты». Подсчитаем сначала число различных сот порядка и, включая случаи, когда все ячейки запретные (все элементы булевой матрицы — нули) и когда все ячейки свободные (все элементы булевой матрицы — единицы). Так как соты порядка и содержат ие ячеек, то число сот с й запретными ячейками равно С„. Следовательно, искомое число равно и' ~ С„= 2". (21.!) Аналогично можно подсчитать, что число сот размера т Х и равно 2 '". С точки зрения пересчета не все соответствующие задачи нужно различать.
Например, все и' задач с одной запретной *) В оригинале «саз)ег». (Лриж перев.) 133 ячейкой, по существу, неразличимы. Поэтому общее число различных с этой точки зрения задач трудно определить. Задачи такого типа будем называть задачами о размещении А неразличимых объектов в соты размера пг ',к,п. К ним относятся, например, некоторые задачи $ 18 с сотами размера 1 к', п и без запретных ячеек. Будем предполагать, что выполняются условия: соты имеют порядок а; в ячейке не более одного объекта (т. е. О или !); каждая строка н каждый столбец содержат не более одного объекта.
! 2 3 4 5 6 7 ! 2 3 4 5 6 7 Рис. 43. Рис. 42. Эту задачу часто называют задачей о ладьях, если имеются в виду ладьи на шахматной доске, не бьющие друг друга, или задачей о назначениях й работников на а должностей, причем каждый работник может занять только одну должность и каждая должность может быть занята только одним работником, В $ б1 мы увидим, что эта задача связана с понятием паросочетания в теории графов. На рис.
42 представлен пример такой задачи с а = 7, и рис. 43 показывает, как поместить пять объектов в соты. Для решения таких задач с помощью денумераторов будем пользоваться формулой включения и исключения из э 12. Рассмотрим 3 свойств, О ( 3 ( а' (п — порядок сот): У,: 1, занимает ячейку 1о б7,: Ц занимает ячейку 13, У,: 1, занимает ячейку 1,.
Некоторые из этих свойств совместимы, другие — нет, например, если в какую-либо ячейку уже помещен объект, то ни в какую ячейку в том же столбце или той же строке нельзя поместить !34 другой объект. Пусть А; — подмножество перестановок со свойством Уи а Ат — подмножество перестановок со свойством У;. Тогда Аа Д А! — — Я, если У~ и Ут соответствуют ячейкам одной и той же строки или одного и того же столбца.
(21.2) Выберем г свойств из и (указанных (г (и). Тогда п — г объектов можно разместить (и — г) ! способами по остальным ячейкам. Обозначим через р„г ( п, число не- пустых пересечений вида З 3 4 3 (Аз, ПА~,П . ПА1„). Тогда в силу(!2.17) с те(г)=р,(п — г)! г=О, 1, 2, ..., и, з (2! .3) 3 имеем 4 и'(г) =се(0) + ю(1) г+ и(2) гт+ ...
+ +те(п)г" + ..., в(п+!)=О, />О, (21.4) Рис. 44. и Ят'(г) = Ю'(0) + В' (1) г + Чт (2) г' + ... -1- Ю' (и) г" -1- ..., ИР (и + 1) = О, ! ) О, (2 1,5) где через йт(г) обозначено число перестановок в точности с г свойствами. Согласно (!2.54) а а Ф'" (г) = ~ се (г) (г — 1)' = ~ р, (п — г)! (г — 1)'. (21.6) т 3 т=а Запишем производящую функцию для р,: а р'(г) =,у~а р,г'. l о (21.7) Производящие функции для задач о сотах будем обозначать через л М' (г) = ~а р, (п — г)! (г — 1)'.
(21.8) Полиномы р'(г) называются ладетуными мноеочленами, а й(*(г) — мноеочленами попаданий. П р и м ер. На рис. 44 изображены соты порядка 6 с шестью запретными ячейками Уь Уз, ..., Уа'). Подсчитаем р„г = = О, 1, 2, 3, 4, 5. ') Для изображения запретных ячеек будут использоваться те же сииво. лы, что в для соответствующих свойств У.
!33 Имеем рз=! (2!.9) р, = 6. (21.10) Заметим, что пары У, н У„У, и У4, У, и Уз несовместимы. Следовательно, Рз= 12, (21, 11) 3-выборок иэ обшего Легко убедиться, что 11 неупорядоченных числа Се=20 несовместимы. Поэтому з р„= 9. (21, 12) Аналогично получаем Рз = 2 Р,=О, р,=О. (21.13) (21, 14) (21. 15) Следовательно, р' (г) = 1 + 6г + 12гз -+ 9гз -1- 2г4 (21.16) Отсюда в силу (21.3) находим за(г): ю(0) =120, ы(1) =144, ю(2) =72, за(3) = 18, зе(4)=2, за(5)=0, (21. 17) в'(г) = 120+ 144г+ 72гз+ 18гз+ 2г', (21,18) Вычисляя Ф' (0) = ж (0) — за (1) + ы (2) — ы (3) + зе (4) — ы (5) = = 120 — 144+ 72 — 18+ 2 = 32, К (1) = ы (1) — Сзза (2) + Сзы (3) — Сю (4) + Сзгз (5) = =144 — 2 72+ 3 18 — 4 2=46, )Р'(2) = в(2) — Сзпз (3) + Сзв (4) — Сзю (5) = 72 — 3 18+6 2=30, )Р'(3) =я(3) — Сын(4) + Сзы(5) = 18 — 4 2 = 10, (21.19) К (4) = пз (4) — Сзю (5) = 2, Т(5) =ю(5) =О, имеем 136 М*(г) = 32+ 46г+ 30г'+ 1Ог'+ 2г'.
(21,20) Это же получается и иэ (21,6): )у" (г) = пз (0) + пз(1) . (г — 1) + ы (2) (г — 1)' -1- за (3) . (г — 1)з -1- + и (4) . (г — 1)з + цз(5) . (г — 1)з + пз (6) . (г — 1)з = = 120 + 144 (г — 1) + 72 (г — 1)з + 18 (г — 1)з + 2 (г — ! )4 = = 32+ 46г + 30гз + 10гз -1- 2гз (21 21) Разложение на минимальные непересекающиеся подсоты.
Будем рассматривать подсоты сот порядка п. Например, соты на рис. 46 — подсоты сот на рис. 45. Пусть С1 и Са — подсоты сот С. Назовем С1 н Са непересекающимися, если запретные ячейки С1 не лежат на столбцах и строках, образующих Са. Например, на рис. 47 подсоты, образованные строками и столбцами соответственно 1, 2, 3 и 4, 5, 6, 7, не пересекаются. Для разложения сот на минимальные') непересекающиеся подсоты достаточно заметить, что если запретна ячейка (1,/), 1 2 3 4 5 6 7 1 2 3'4 6 6 7) ~ 1'1 121 3 5 6 ,' 5 ,' 16, , '7,' Рис 47.
Рис. 46. Рис. 45. то строки и столбцы с пндексамн 1 и 1 принадлежат одним и тем же подсотам. Возьмем, например, соты на рис. 48. Выписываем в столбец индексы, соответствующие одним и тем же подсотам, начиная с 1: 2 3 4 6 8 5 7 9 Таким образом, получаем следующие 5 минимальных непересекаютцихся подсот: С, — с индексами 3, 5, Ст — с индексами 1, 9, 8, Са — с индексом 4 (без запретных ячеек), С4 — с индексами 6 и 7, Са — с индексом 2 (см, рис.
49). Разложение на минимальные непересекающиеся подсоты единственно, что легко доказать, Теорема. Пусть С, и С,— непересекающиеся подсоты, на которые разлагается С. Тогда Р' (г) = Р',(г) Р',(г), (21.23) где р*(г), р',(г), р.,*(г) — соответствующие ладейные ланогочлены для С, С„С,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
