Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 94
Текст из файла (страница 94)
Снова рассмотрим доску, изображенную на рис. 12.12. с Рис. 12Л2 Имеем 17(х, С| ) = 1 + 3х + хз В(х, Сз) = 1 + 4х + 2х~. Следовательно, В(х, С1) = з1(х, С1)Л(х, Сз) = = (1+ Зх+ ха)(1+ 4х+ 2ха) = = 1+ 7х + 15х~ + 10х~ + 2х'. Существует еще один способ нахождения Л(х, С) путем разбиения С на доски. В этом случае доски могут иметь общие строки и столбцы. ТЕОРЕМА 12.23.
Пусть задана доска С, пусть з — квадрат доски С. Пусть С, — доска С, в которой удален квадрат з. Пусть Сн — доска С, в которой удалены строка и столбец, содержащие удаленную клетку з. Тогда В(х, С) = хВ(х, С4') + В(х, С,). ДОКАЗАТЕЛЬСТВО. Пусть й — положительное целое число. Если 1 неатакуюших падей помещены на доске С и она имеет пт клеток, то на клетке з либо есть ладья, либо ее нет.
Если ладья помещена на клетке з, то остальные й — 1 ладей должны быть выбраны из доски С4~, что можно осуществить гь 1(С,'Е) способами. Если ладья не помещена на клетке з, то 1: ладей должны быть выбраны из доски С„что можно осуществить гь(С,) способами. Следовательно, гь(С) = гь 1(С~~) + гь(С,), и поскольку го(С) = го(С,) = 1, п~ 7П йп гь(С)х" = У гь ~(С~~)х" + ~~~ гь(С,)х". а=о а=1 а=о 514 ГЛЯод 12. Снова о комбинаторных подсчетах Но 'У'ть,(С№)хь = ~~ ' т„(С№)х'+' = х ') т„(С№)х" = х,"У'т,(С№)х", поскольку т (С№) = О, что должно равняться б, т.к.
С№ содержит менее т клеток. Следовательно, В(х, С) = х11(х, С№) + В(х, С,). ПРИМЕР 12.24. Пусть С вЂ” доска, изображенная на рис. 12.13, где а — отмеченная клетка. В таком случае С, — доска, изображенная на рис. 12.14, и доска ѹ— фигура, изображенная на рис. 12.!5. Рис. !2.!5 Рис.
!2.14 Рис. 12.!3 Ладейные полиномы имеют вид В(х, С,) = 1 + бх + бх В(х, С№) = 1 + 4х + 2хг. Следовательно, Я(,С) =хк,х,с№)+П(*,С,) = = х(1+4х+2хг) +1+бх+бхг = = 1+ 7х + 10хг + 2хз ПРИМЕР 12.25. Пусть С вЂ” доска, изображенная на рис. 12.16, где а — отмеченная клетка. Тогда С, — доска, изображенная на рис. 12.17, и С№ — доска, изображенная на рис. 12.18. Рис. !2.И Рис.
!2.!7 Рис. !2.!6 РАЗДЕЛ 12.4. Ладейные попиномы и запрещенные позиции 515 1т(х, С,) = тс(х, С,'))т(х, Сн), где С,' — верхний левый прямоугольник и Сп — нижний правый квадрат. 11(х, С,') = 1+ 2х В(х,Сн) = 1+4х+ 2х . Следовательно, В(х,С,) = (1+2х)(1+4х+2хз) = 1+бх+10хз+4хз. Легко заметить, что В(х, С№) = 1+ Зх+ 2х~. Следовательно, Л(х, С) = хВ(х, С№) + )1(х, С,) = = х(1 + Зх + 2х~) + 1 + бх + 10х + 4х = 1+7х+13хз+бх . Изучению ладейных полиномов было уделено достаточно времени, поэтому представляется разумным теперь указать на некоторое их применение.
Вспомним перестановочные матрицы. Каждая из них имеет только по одной единице в каждой строке и в каждом столбце, и нули — во всех остальных позициях. Если ладьи отождествлять с единицами, то перестановку п элементов можно отождествить с размещением п неатакующих ладей на шахматной доске размером и х и. Если рассматривать перестановку ф на п элементах как функцию, то ее можно представить как множество упорядоченных пар 1(к, ф(к)): й = 1,2, 3,... п). Если отождествить упорядоченную пару (Е,ф(й)) с клеткой шахматной доски, лежащей на пересечении строки Й и столбца ф(й), то опять приходим к размещению и неатакующих падей на шахматной доске размером и х и.
Поэтому различные перестановки на и элементах можно отождествлять с различными расположениями п неатакующих падей на шахматной доске размером и х и. Предположим, что студент хочет прослушать 5 различных дисциплин в течение пяти различных лекционных часов. Если изобразить ситуацию с помощью шахматной доски, то ее заштрихованные области могут изображать лекционные часы, когда требуемые дисциплины не читаются. Пусть ф отображает каждую дисциплину на период, когда ее читают.
Как и ранее, будем рассматривать ф как перестановку. В таком случае, у нас имеются те значения и, которые не должна принимать функция ф(н). Например, предположим, что и = 5, и ф(1) не должно принимать значения 2, 3 или 5; ф(2) не должно равняться 1, 2 или 3; ф(3) не должно равняться 1, 3 или 5; ф(4) не должно принимать значения 1, 2 или 5 и ф(5) не должно быть равно 1, 3 или 4. Перестановки, удовлетворяющие этим ограничениям, называются допусгпимыми размещениями на доске.
Запрещенная область, или запрещенные позиции, — это то, что принадлежит заштрихованной области шахматной доски, изображенной на рис. 12.19. 516 ГЛАВА 12. Снова о номбвнвторных подсчетах 12 34 5 1 2 3 4 5 Рис. !2.!9 Р . !2.2О Вполне очевидно, что допустимыми размещениями являются 1 2 3 4 5 1 4 2 3 5 Предположим теперь, что клеток в запрещенной области сравнительно мало. Пусть имеется доска, запрещенная область которой изображена на рисунке 12.20. Работать с запрещенной областью, которая весьма мала, гораздо проще. Предположим, что имеется доска размером п х п, у которой запрещенная область А относительно мала.
Пусть А, — множество всех перестановок ф таких, что ф(!) принадлежит запрещенной области А. В таком случае нас интересует (А' Г~ А' и... Г1 А'„). Но )А', Г1А~ й... йА'„! = п! — ~~у (А,)+ ~)А, й А~)— 1 а<1 — ~А, а А а Аь~ + + ( — 1)" (А~ П Аз Г~... Г1 А„~, 1<!<Ь поэтому необходимо найти значения всех членов, входящих в правую часть уравнения. Рассмотрим )А,( для фиксированного значения 1. Пусть п; — количество клеток запрещенной области, которые находятся в строке 1. Тогда существуют п; способов выбора ф(г) таких, что 4(г) принадлежит А;.
Но для й ф г' функция р(й) может принимать любое значение, поскольку ф является перестановкой. Следовательно, имеются (п — 1)! способов выбора других значений функции б, Следовательно, и в области А, существуют п;(п — 1)! перестановок. Суммируя, получаем ~А,~ = ~п,(п — 1)! = ~~~ п, (п — 1)!. Но Д;, и;) = г1(А), количеству клеток в запрещенной области А. Следовательно, ~~) )А,~ = г1(Аип — 1)!. Теперь рассмотрим ~, . )А, й А ~. Пусть ! и 1 — фиксированы. Чтобы ф принадлежало А, Л А, требуется, чтобы ф(г) и фО) — принадлежали области А и находились в различных столбцах. Пусть 1 е1 и; — количество способов таких, РАЗДЕП 72.4. Падейные полиномы о запрещенные позииии 517 что ф(г) и ф(з) — принадлежат области А и не находятся в одном и том же столбце, Поэтому существуют и, способов выбора ф(г) и ф(з).
Для )с ф г, з значение ф(й) может быть любым, поскольку ф является перестановкой. Следовательно, имеются (п — 2)! способов выбора другого значения функции ф. Следовательно, А, й А, содержит п„(п — 2)! перестановок. Суммируя по г и з, получаем ~~А,Г!Аз~ = ~~~ п; (п — 2)! = ~п;, (и — 2)!. а<з х<з а<з Но 2.',<, и,, — всего лишь количество способов, которыми можно расположить две неатакующие ладьи в области А. Поэтому 2;,< иГз = гз(А) и ~~) (А,! = гз(А)(п — 2)!. Аналогично, для нахождения ~;п~,н ~, !А„Г1 А;, й Г! Аь„! положим и„ „ ,„, равным количеству способов таких, что ф(зг), ф(гз),..., ф(! ) все принадлежат области А н не находятся в одном столбце.
Поэтому имеются ип „ способов выбора ф(з1), ф(ез),..., ф(1 ). Для Л ~ гы гз,..., з значение ф(Л) может быть любым, поскольку ф — перестановка, Следовательно, имеются (и — т)! способов выбора другого значения для ф, и Аи аА,,Г! . Г!Аг„содержит и„„;,(и— т)! перестановок. Суммируя по гы гз, ..., г, имеем !А,, П А„Г! Г! А, ! = ~~~ п„„, „(п — тп)! = и<аз«" * и<зз«" а и„...
(и — ги) !. ! и<аз«" 1 Но 2, <„«, пч „; — всего лишь количество способов размещения т неатакующих падей в области А. Следовательно, 2;,. <,, «, и„;,, = г (А) н !Ап Г! А, Г! . Г! А; ! = г,„(А)(п — т)!. и<ая« "~ Поэтому !А' Г! А' Г!... Г! А'„! = и.' — г1(А)(п — 1)! + гз(А)(п — 2)! + .. + ( — 1)" г„(А), где ладейный полином для области А, В(х, А) = ~„" гь(А)хь. ПРИМЕР 12.26. Рассмотрим доску, изображенную на рис. !2.2!, где заштрихованная область А — запрещенная зона.
Найдем количество допустимых размещений. Рис. !2.21 518 ГЛА8А 12. Снова о комбинаторнык подсчетах Требуется найти !А1Г!АзГ!АзГ!А4Г!АзПАа) =6! — г1(А) 5!+гз(А) 4!+ ° +( — 1) га!А). Уже известно, что полином ладьи для области А имеет вид В(х, А) = 1 + 7х + 15хз + 10хз + 2х4, поэтому количество допустимых размещений определяет соотношение )А1 Г! А~ П А~з Г! А4 Г! А~ Г! А~! = 6! — 7 5! + 15 .
4! — 10 . 3! + 2. 2! = 184. П ПРИМЕР 12.27. Рассмотрим доску, изображенную на рис. 12.22, где заштрихованная область А — запрещенная зона. Найдем количество возможных размещений. Рис. !2.23 Рис. 12.22 Требуется найти !А', Г! Аз Г1 Г! Ат! = 7! — г1(А) . 6)+ гз!А ) . 5! +. + ( — 1)~гт(А), поэтому нужен ладейный полипом для области А.
Заметим, что на доске, изображенной на рис. 12.23, заштрихованная область В имеет такой же ладейный полипом, как и область А. Заштрихованная область В состоит из областей Вы Вз и Вз, у которых нет общих строк и столбцов. Поэтому Их, А) = Я(х, В) = В(х, В1) . Л(х, Вз) В(х, Вз). Поскольку В(х, В,) = 1 + 4х + 2хз; В(х, Вз) = 1 + Зх; Я(х, Вз) = 1 + 2х то имеем В(х, А) = (1+ 4х + 2х )!1+ Зх)(1+ 2х) = ! 0~ ! 28~2 + 34 3 ! 12~4 Следовательно, !А', Г! А', Г! Г! АЯ = 7! — 9 6! + 28 5! — 34 4! + 12 3! = 1176, так что количество возможных размещений равно 1176. РАЗДЕЛ 12.4. Лодейные попиномы и запрещенные позииии 519 ° УПРАЖНЕНИЯ 1. Найдите ладейный полипом для доски, изображенной на рис.
12.24. 2. Найдите ладейный полипом для доски, изображенной на рис. 12.25. Рис. 12.25 Рис. 12.24 3. Найдите ладейный полипом для доски, изображенной на рис. 12.26. 4. Найдите ладейный полипом для доски, изображенной на рис. 12.27. Рис. 12.2б Рис. 12.27 5. Найдите ладейный полином для доски, изображенной на рис. 12.28. 6. Найдите ладейный полином для доски, изображенной на рис. 12.29.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
