Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 92
Текст из файла (страница 92)
Попробуем найти количество разупорядочений для и = 4, используя технику подсчетов. Пусть ЕУ вЂ” множество всех перестановок на множестве 11,2,3,41. Таким образом, (ЕУ) = 4!. Пусть А~ — множество перестановок, оставляющих на месте символ 1, Аз — множество перестановок, оставляющих на месте символ 2, Аз — множество перестановок, оставляющих на месте символ 3 и А4 — множество перестановок, оставляющих на месте символ 4. В таком случае, множество А', й Аз Г~ Аз П А4 — множество перестановок, не оставляющих на месте нн один из символов. По теореме о включении-исключении )Аг йА~~ Г1Аз йА,',) = (ЕУ! — ~~~ (А,)+ ~~> (А, Г)Ах)— а«а а<х«а — (А, Г~ А, Г~ Аь) + (Аг П Аз г~ Аз П Аз ).
~<~<а<<4 Пусть А;, =А,йА, А,ь =А,Г~А ПАь и Агаве — — АгГ1АзПАзйА4. Таким образом, А„— множество всех перестановок, оставляющих на месте символы г и з, А;,» — множество перестановок, оставляющих на месте символы г, у и к, и РАЗДЕЛ !З.З. Общее включение-исключение и разупорядочения 505 множество А1ззз содержит только тождественную перестановку, которая оставляет на месте все четыре символа.
Для нахождения суммы ~,<4(А,( требуется найти количество перестановок, оставляющих на месте символ з. Рассмотрим, в частности, Аы Любая перестановка из А1 оставляет символ 1 на месте и переставляет символы 2, 3 и 4. Следовательно, множество А1 содержит 3! перестановки. По аналогичным соображениям, множество А, содержит 3! элемента.
Следовательно, (А1) + !Аз) + !Аз) + (А4) = 4 х 3! = 4! = 4! х —. 1 1! ' Найдем теперь )А, О Аз! = ~ (А,.!. «<у<4 «<З<4 Рассмотрим частный случай !А1з~. Чтобы принадлежать множеству А1з, перестановка должна оставлять на месте символы 1 и 2 и переставлять символы 3 и 4.
Для этого существует 2! способа. Таким образом, !А1з! = 2. Аналогично, )А;,! = 2 при всех 1 < г < з < 4. Теперь возникает вопрос, сколько имеется таких множеств А„Р Поскольку символы 1 и з выбираются из 4 элементов, то существуют (~~) множеств вида А«у Следовательно, ~А,,~ = ~ ~ 2! = —,,2! = 4! —. /4««4! 1 «<«<е Далее найдем !А, г! А г! Аь! = ~ |А; ь1. '<у<к<4 «<з<ьбз Сначала рассмотрим А1зз. Поскольку символы 1, 2 и 3 не меняют своих мест, то остается только 4. Отсюда, множество А|аз содержит только 1 элемент.
Аналогично, множество Аю» при 1 < г < з < к < 4 содержит только 1 элемент. Поскольку символы г, з и к выбираются из 4 элементов, то существуют (4д) множеств вида А, ы Следовательно, 4! 1 )А, «)= —, х1=4! —,. «<1<к<4 Наконец, множество Ащз4, как уже отмечалось, состоит из 1 элемента, но 4! 1 1= — =4! х —.
4! 4! Сводя вместе полученные результаты, получаем ~А', О А«з О Аз О А', ~ = 4! — 4! х — + 4! — — 4! — + 4! х— 1! 2! 3! 4! 1 1 1 1 = 4!(1 — — + — — — + — ). 1! 2! 3! 4! В более общем виде можно сформулировать следующую теорему. 506 ГЛЯВА 12 Снова о комбинаторных подсчетах ТЕОРЕМА 12А1. Для и > 1 величина Р„, количество разупорядочений на и символах 1,2,3,...,и, вычисляется по формуле 1 1 1 В„= и! 1 — — + — — — + + ( — 1)" — ?). 1! 2! 3! и!)' ДОКАЗАТЕЛЬСТВО. Для доказательства этого утверждения рассмотрим А1 Г! Азг!Азг!...Г!Ах при 1 < к < и.
Любой элемент множества А1Г!АзГ!АзП...Г!Аь оставляет на месте символы 1, 2, 3,... и, поэтому он переставляет и — й символов. Следовательно, !А, Г1 Аз Г! Аз Г!... Г! Аь~ = (и — к)!. Аналогично, для любых фиксированных тытз,тз,.,.ть имеем )А, Г! А„„Г! А, Г!... Г! А, ! = (и — Й) !. Поскольку ?с символов выбираются из и символов, то существуют ("„) множеств вида А , Г! А , П А , Г1...Г! А „. Следовательно, ~~А,ох,ох,~...~х,~-() [ — и!- тЙ х (и — Й)! = и! х —. Ы(и — й)! к! Снова предположив, что сг — множество всех перестановок и объектов, так что (Ц = и!, получаем И„= ~ А', Г! А', Г! А', Г!... Г! А'„~ = ! и~ — ',У !А, ! + ~ !А, Г! А, (— $ т<1 — !А; Г1 А Г! Аь! + + ( — 1)"!А1 Г! Аз Г!... Г1 А„~ = а<у<а 1 1 1 „1 = и! — — и! + — и! — — и! + + ( — 1)" — и! = 1! 2! 3! и! 1 1 1 „1 ! (1 — — + — — — +...
+ ( — 1)" — ) . 1! 2! 3! и! В математическом анализе показано, что это разложение в ряд Тейлора функции е ' имеет вид 1 1 1 1 1 е — 1 1! 2! 3! 4! 5! Следовательно, Р„ = и!е ПРИМЕР 12А2. Неопытный официант подает 10 различных блюд, обслуживая 10 клиентов. Сколькими способами он может сделать так, чтобы ни один клиент не получил свой заказ? В данном случае имеет место хаотическая перестановка 10 объектов, поэтому количество таких перестановок равно 1 1 1 1 1 1 1 1 1 1 10! (1 1! 2! 3! 4! 5! 6! 7! 8! 9! 10! ' РАздел 12.3. Общее еключение-исключение и разулорядочения 507 ПРИМЕР 12.13. Матрицей перестановок размерности 8 х 8 является матрица, в каждой строке и в каждом столбце которой только один элемент равен 1, а все остальные равны О.
Сколько существует матриц перестановок размерности 8 х 8, содержащих на главной диагонали только нули? Такие матрицы являются матричными представлениями перестановок 8 символов, которые и являются разупорядочениями. Следовательно, имеется 1 1 1 1 1 1 1 1 1! 2! 3! 4! 5! 6! 7! 8! таких матриц. П ПРИМЕР 12.14. В шахматах две ладьи (туры) могут атаковать друг друга, если они расположены на одной вертикали (столбце) или на одной горизонтали (строке). Следовательно, неатакующие ладьи — это те, которые расположены в разных столбцах или в разных строках.
Очевидно, что восемь неатакующих падей можно расположить на стандартной (8 х 8)-клеточной шахматной доске. Сколькими способами это можно сделать? Поскольку размещение на шахматной доске неатакующих ладей эквивалентно размещению единиц в перестановочной матрице, и существуют 8! перестановок на 8 объектах, то существуют 8! различных перестановочных матриц размерности 8 х 8. Если не привязываться к перестановочным матрицам, то расположение ладьи в г-ой строке и в ~-ом столбце можно идентифицировать с упорядоченной парой чисел (г,7). Если это сделано для каждой ладьи, то в результате имеем 8 упорядоченных пар,что дает перестановку, в которой первый элемент каждой упорядоченной пары отображен на второй элемент.
В данном случае имеем стандартное представление функции как множества упорядоченных пар. П ПРИМЕР 12.15. Сколькими различными способами можно расположить на стандартной (8х8)-клеточной шахматной доске 8 неатакующих ладей, чтобы у каждой номер строки и номер столбца не совпадали? Итак, ладья, расположенная в г-ой строке, не может находиться в 1-ом столбце. Количество таких размещений равно количеству перестановочных матриц, у которых отсутствуют единицы на главной диагонали (там только нули). В терминах перестановок это означает, что ни один элемент не отображается сам на себя. Следовательно, существуют 1 1 1 1 1 1 1 1 1! 2! 3! 4! 5! 6! 7! 8! 8! (1 различных способов разместить ладьи.
° УПРАЖНЕНИЯ 1. Докажите, что для любого положительного целого числа и — + — + +( — 1)" =О. 2. У преподавателя обучаются 25 студентов. Преподаватель проводит тест, а затем просит студентов обменяться бумагами так, чтобы никто не проверял свой ответ. Сколькими способами это можно сделать? 508 ГЛАВА 12. Снова о комбинаторных подсчетах 3. Студент сдает экзамен, в процессе которого на каждый из 15 вопросов он должен выбрать один из 15 ответов. Если никакие два вопроса не имеют совпадающих ответов, то сколькими способами студент может дать неправильный ответ? 4. Пусть А = (1, 2, 3, 4, 5, 6, 7, 8, 9) и В = ( — 1, — 2, — 3, — 4, — 5, — 6, — 7, — 8 —, 9) Каждому элементу из первого множества нужно поставить в соответствие единственный элемент из второго множества.
Элементы каждой пары суммируются. Сколькими способами можно образовать пары, так чтобы ни одна из сумм не равнялась нулю? 5. Неграмотный почтальон должен доставить по одному письму каждому из 7 своих клиентов. а) Сколькими способами он может доставить письма, так чтобы ни один из клиентов не получил свою почту? б) Сколькими способами он может доставить письма, так чтобы хоть один клиент получил свою почту? в) Сколькими способами он может доставить письма, так чтобы только один клиент получил свою почту? г) Сколькими способами он может разнести письма, так чтобы только один клиент не получил свою почту? 6.
Пусть множество А содержит 12 элементов, и у — перестановка элементов множества А. Пусть Я = (д: Π— перестановка на множестве А и О(а) ~ р(а) дя всех а е А). Найдите ~Я~. 7. Семь джентльменов отправляются на вечеринку и сдают там свои шляпы. Сколькими способами непутевый гардеробщик может вернуть шляпы, так чтобы а) ни один из джентльменов не получил свою шляпу? б) только один из джентльменов получил свою шляпу? в) хоть один из джентльменов получил свою шляпу? г) хотя бы двое джентльменов получили свои шляпы? 8.
Сколько существует перестановок элементов множества (1,2,3,4,5,6,7,8,9) таких, что а) в каждой перестановке ни один элемент не остается на своем месте, т.е. перестановка не отображает ни одно из чисел само в себя? б) перестановка не оставляет ни одно четное число на своем месте? в) перестановка оставляет на своем месте хотя бы одно четное число? г) в результате перестановки в точности четыре числа остаются на своем месте? 9. Используя предыдущую задачу в качестве схемы, определите количество перестановок на и элементах, в результате которых в точности й элементов остаются на своих местах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
