Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 93
Текст из файла (страница 93)
10. Найдите количество положительных целых чисел, меньших или равных чис лу 2300, взаимно простых с числом 700. 11. Найдите количество положительных целых чисел, меньших или равных числу 5460, взаимно простых с числом 700. РДЗДЕЛ 12.4. Падейные полиномы и запрещенные позиции 509 12.4. ЛАДЕЙНЫЕ ПОЛИНОМЫ И ЗАПРЕЩЕННЫЕ ПОЗИЦИИ В приведенных выше примерах на (8 х 8)-клеточной шахматной доске было изучено расположение неатакующих падей, а также расположение ладей на шахматной доске, когда они не могут находиться на пересечении строки и столбца, номера которых совпадают. Клетки шахматной доски, на которых ладья не может быть расположена, можно представить себе как запрещенные позиции.
Рассмотрим теперь шахматную доску или часть шахматной доски с запрещенными позициями. При использовании такой (и х п)-клеточной шахматной доски ситуация также описывается как перестановки с запрещенными позициями по аналогии с перестановками неатакующих ладей. До того, как у читателей, не играющих в шахматы, возникнет желание пропустить этот раздел или отложить книгу в сторону, заметим, что шахматы и шахматная доска используются только потому, что они хорошо иллюстрируют то, что мы собираемся делать.
Начнем с введения ладейного полинома. ОПРЕДЕЛЕНИЕ 12.16. Пусть С вЂ” произвольная доска с т квадратами, которая для некоторого целого числа п является частью их и-клеточной шахматной доски. Для О ( й ( т целое число гь(С) равно количеству способов, которыми й ладей могут быть размещены на доске С в неатакуюших позициях. Ладейним полиномом гт(х, С) на С называется производящая функция для чисел гь(С), так что Жх С) го(С) + гг(С)х + гг(С)хг + гз(С)х + ° ° + г (С)х ПРИМЕР 12.17. Пусть С вЂ” доска, изображенная на рис.
12.8. Всегда имеется способ разместить О падей на доске, поэтому го(С) = 1 для любой доски С. В этом случае имеются три способа разместить на С одну ладью, поскольку ее можно расположить в любой клетке доски С. Расположить две ладьи в неатакующей позиции можно только одним способом. Следовательно, Д(х, С) = 1+ 3х + хг Рис. Г2.9 ПРИМЕР 12.18. Пусть С вЂ” доска, изображенная на рис. 12.9. Доска состоит из 8 блоков, поэтому имеются 8 способов расположить одну ладью на доске С. Для размещения двух ладей в неатакуюшей позиции имеются 4 способа выбора на верхней горизонтали и три места для размещения ладьи на второй горизонтали, поскольку ладьи не могут располагаться друг под другом. Значит, существует всего 12 возможных способов расположения двух неатакующих падей.
Следовательно, В(х, С) = 1+ 8х + 12хг 510 ГПЯВА 12 Снова о комбинаторнык подсчетах ПРИМЕР 12.19. Пусть С вЂ” доска, изображенная на рис. 12.10. Чтобы упростить задачу, заметим, что доску С можно представить состоящей из двух частей, Сг и Сэ, как показано на рисунке. Поскольку обе части не имеют ни общих строк, ни общих столбцов, то размещение ладей в одной части не влияет на размещение ладей в другой части. с Рис.
!2.(0 Для размещения одной ладьи на С нужно разместить ее либо на Сы либо на Сз. Имеются 3 способа размещения одной ладьи на С~ и 4 — на Сз, поэтому есть 7 способов размещения ладьи на доске С. Для размещения двух неатакуюших ладей на доске С можно размещать их в части Сы одну ладью — в Сг и одну ладью — в Сз или обе — в Сз.
Имеется 1 способ разместить две ладьи в части С~ и 3 способа размещения ладьи в части С~ и 4 — в части Сз, что дает 12 способов размещения 1 ладьи в части Сг и одной ладьи в части Сз. Есть 2 способа размещения двух неатакующих ладей в части Сз. Таким образом, существуют 1 + 12 + 2 = 15 способов размещения двух неатакуюших ладей на доске С. Чтобы разместить 3 ладьи на доске С, можно две ладьи разместить в части С~ и одну ладью — в части Сз, или наоборот. Имеется 1 способ размещения двух неатакующих ладей в части Сг и 4 способа размещения одной ладьи в части Сз, что дает 4 способа размещения двух ладей в части Сг и одной ладьи — в части Сз.
Есть 3 способа размещения одной ладьи в части Сг и 2 способа размещения двух неатакущих ладей в части Сз, поэтому существуют 6 способов размещения двух ладей в части Сз и одной ладьи — в части Сы Это даст всего 4+ 6 = 10 способов размещения 3 ладей на доске С. И наконец, чтобы разместить четыре неатакующие ладьи на доске С, можно две неатакующие ладьи разместить в части Сг и две — в части Сз. Имеется 1 способ размещения двух неатакуюших ладей в части Сг и 2 способа размещения двух неатакуюших ладей в части Сз. Поэтому есть 2 способа размещения четырех неатакующих ладей на доске С. Таким образом, ладейный полипом для доски С имеет вид 77(х, С) = 1 + 7х + 15х~ + 10хз + 2х~. ПРИМЕР 12.20.
Пусть С вЂ” доска, изображенная на рис. 12.11. Как и в предыдущем примере, доску С можно представить состоящей из двух частей, Сг и Сз, как показано на рисунке. Поскольку обе части не имеют ни общих строк, ни общих столбцов, то размещение ладей в одной части не влияет на размещение ладей в другой части. РАЗДЕЛ 12.4. Ладейные попиномы и запрещенные позичии 611 с, Рис. !2.Л Имеются 5 способов размещения ладьи в части Сг и 8 — в части Сз. Поэтому существуют 13 способов размещения ладьи на доске С. Отметим, что г~(С) = г~(С~) + с~(Сз). Учитывая, однако, что го(С~) = го(Сз) = 1, можно положить г~(С) = г~(С~)го(Сз) + го(С )г~(Сг).
При выборе двух неатакующих ладей можно выбрать две ладьи из части Сг, одну ладью из части Сс и одну — из части Сз или выбрать две ладьи из части Сз. Имеются 4 способа выбора двух неатакуюших ладей из части Сы Есть 5 способов выбора одной ладьи из части С~ и 8 способов выбора одной ладьи из части Сз. Следовательно, имеются 5 х 8 = 40 способов выбора 1 ладьи из части С~ и 1— из части Сз. Имеются 12 способов выбора двух неатакующих ладей из части Сз.
Следовательно, существуют 5+ 40+ 12 = 56 способов расположения двух неатакуюших ладей на доске С. Согласно методу выбора имеем, что гз(С) = гз(Сг) + г~(Сг)гг(Сз) + гз(Сз), н это можно переписать в виде гз(С) = га(С,)го(Сз) + г~(С~)гг(Са) + го(Сз)га(Сз), Далее, чтобы получить 3 неатакующие ладьи на доске С, можно попробовать получить 3 неатакующие ладьи из части Сы но такой возможности нет. Можно получить одну ладью из части Сз и две неатакуюшие ладьи из части Сз.
Имеются 5 способов получить одну ладью из части Сг и 12 способов получить две неатакующие ладьи из части Сз. Это дает 5 х 12 = 60 способов получить три неатакующие ладьи, располагая одну ладью в части Сз и две неатакуюшие ладьи в части Сз. Также можно получить две неатакуюшие ладьи из части Сг и одну ладью из части Са. Имеются 4 способа получить две неатакующне ладьи из части С~ и 8 способов получить одну ладью из части Са. Следовательно, существуют 4 х 8 = 32 способа получить три неатакуюшие ладьи, располагая две неатакуюшие ладьи в части Сг и одну ладью в части Са.
Снова можно попробовать расположить три неатакуюшие ладьи в части Сз, но такого способа нет. Следовательно, существуют гз(С) = 60+ 32 = 92 способа расположить три неатакуюшие ладьи на доске С, В соответствии с методом выбора можно также записать гз(С) = гз(С~)г~(Сз) + г~(С~)гз(Сз). 512 ГпявА д2. снова о комбинаторных подсчетах Наконец, чтобы расположить четыре неатакующие ладьи на доске С, нужно две неатакуюшие ладьи получить из части Сд и две неатакуюшие ладьи — из части Сг.
Имеются 4 способа получить две неатакующие ладьи из части Сд и 12 способов получить две неатакуюшие ладьи из части Сг. Таким образом, есть 4 х 12 = 48 способов получить четыре неатакуюшие ладьи на доске С. Можно записать, что г4(С) = гг(Сд)гг(Сг). Таким образом, Н(х,С) = 1 + 13х + 56хг + 92хз + 48х4.
А также В(х, С) = го(Сд)го(Сг) + (гд(Сд)го(Сг) + го(Сд)гд(Сг))х+ + (гг(Сд)го(Сг) + гд(Сд)тд(Сг) + го(Сд)гг(Сг))х + + (гг(Сд)гд(Сг) + гд (Сд)гг(Сг))х + гг(Сд)гг(Сг)х4 = = (го(Сд) + (гд(Сд)х+ (гг(Сд)х )((го(Сг) + (гд(Сг)х+ (гг(Сг)х ) = = Л(х, Сд )Л(х, Сг). Следовательно, можно было бы получить ладейный полипом для С, перемножая ладейный полином для части Сд и ладейный полипом для части Сг. Действительно, дд(х, С ) = 1 + 5х + 4хг и В(х, Сг) = 1 + 8х + 12хг, а их произведение Их, Сд) В(х, Сг) = (1 + 5х + 4хг) (1 + 8х + 12хг) = = 1 + 13х + 56хг + 92хз + 48 = дд(х, С). На основе изложенного выше примера приходим к следующей теореме. ТЕОРЕМА 12.21. Если доска С состоит из двух частей, С, и Сг, не имеющих ни общих строк, ни общих столбцов, то д1(х, С) = д1(х, Сд)дд(х, Сг).
ДОКАЗАТЕЛЬСТВО. Рассмотрим коэффициент гь(С) при х" в полиноме В(х, С). Для выбора й неатакующих ладей на доске С следует выбрать 1 из них из части Сд и й — 1 — из части Сг. Существуют гд(Сд) способов выбора 1 неатакуюших падей из части Сд и гд д(Сг) способов выбора й — 1 неатакуюших ладей из части Сг. Это дает гд(Сд)гд д(Сг) способов выбора 1 неатакуюших ладей из части С, и к — 1 неатакующих ладей из части Сг. Если предположить, что 1 принимает все значения от 0 до 15 получим гь(С) = то(Сд)гд(Сг) + гд(Сд)гь д(Сг) +. + гд(С,)гк д(Сг) +.
+ гь(Сд)то(Сг). РАЗДЕЛ 42.4. Лаоейные полиномы и запрещенные позиции 513 Но это не что иное, как коэффициент при х" в произведении )1(х, С1) В(х, Сз) = (го(Сз) + г1(С1 )х + + г„,(С1)х )(го(Сз) + г1(Сз)х+ .. + г,„(Сз)х~). ° ПРИМЕР 12.22.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
