Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 89
Текст из файла (страница 89)
Используя тот факт, что 5„— число возможных способов размещения п (и) различимых объектов в й неразличимых ящиках, ни один из которых не может быть пустым, мы можем найти количество способов размещения и различимых объектов в й различимых ящиках, ни один из которых не может быть пустым. По сути, нам нужно перейти от неупорядоченных ящиков к упорядоченным. При переходе от упорядоченных ящиков к неупорядоченным нужно делить соответствующее количество способов размещения на Ы, как было сделано при переходе от перестановок к сочетаниям.
Поэтому при обратном переходе нужно умножать на 91. Таким образом, существуют ЙБ„" способов размещения и различимых объектов в й неразличимых ящиках, ни один из которых не может быть пустым. Пусть 5 — множество, содержащее и объектов, и Т вЂ” множество, содержащее й объектов. Ранее было подсчитано количество всех функций из 5 в Т, а также количество биективных функций из Я в Т. Теперь мы можем подсчитать количество сюръективных функций из Я в Т.
Представляя й объектов множества Т как ящики, отображение элемента з из 5 в элемент г из Т можно отождествить с размещением объекта з в ящик 1. Поскольку функция сюръективна, то ни один 492 ГЛЛВА 12. Снова о комбинаторных подсчетах из ящиков не будет пустым. Следовательно, существуют йЮ),"~ сюръективных функций из п-элементного множества в и-элементное множество. Теперь мы можем построить следующую таблицу; Количество способов Размещение и объектов в К ящиках С(и~ иг~ пг, из, ' ' ' па) объекты — различимые, ящики — различимые, п, объектов в Ыом ящике (2) объекты — различимые, ящики — различимые, ящики могут быть пустыми 1ЦЮ '* (3) объекты — различимые, ящики — различимые, ящики не могут быть пустыми (4) С(п+ и — 1,п) объекты — неразличимые, ящики — различимые, ящики могут быть пустыми (5) С(и — 1, /с — 1) объекты — неразличимые, ящики — различимые, ящики не могут быть пустыми (6) объекты — различимые, ящики — неразличимые, ящики могут быть пустыми (7) объекты — различимые, ящики — неразличимые, ящики не могут быть пустыми ТЕОРЕМА 12.4.
Завершив рассмотрение размещений объектов в ящики, перейдем к нахождению количества способов разделения и объектов на й-циклы при условии, что никакие два из 1-циклов не имеют общих элементов. Цикл из т объектов имеет виД агагаз а, гДе а,„считаетсЯ сосеДом аы так что агагаз ау а = а .. а агагаз .. а Следовательно, а,агаз = ага~аз = агазаг. Можно представить себе и-цикл как п человек, сидящих за круглым столом. В главе 8 было установлено, что существуют (т — 1)! способов рассадить ги человек за круглым столом. Следовательно, если дано т объектов, то существуют (т — 1)! способов построить т-цикл. Теперь подсчитаем количество способов разделения и объектов на й-циклы при условии, что никакие два из Й-циклов не имеют общих элементов.
ТЕОРЕМА 12.$. Количество возможных способов разделения п объектов на йциклы так, что никакие два из н-циклов не имеют общих элементов, равно з ", где (зь . 0 < и < п) — множество чисел Стирлинга первого рода. 00 ДОКАЗАТЕЛЬСТВО. Пусть У(п,й) — количество возможных способов разделения и объектов на н-циклы, когда никакие два из 9-циклов не имеют общих элементов. Чтобы доказать справедливость соотношения 7"(п, й) = з~~"~, необходимо сначала показать, что 1(и, О) = 0 для всех и > 1.
Но если и > 1, то невозможно РЛЗДЕЛ 12.1. Эедечи о размен(енио 493 сформировать 0 циклов и использовать все п объектов. Следовательно, 1(п, О) = 0 для всех п > 1. Теперь покажем, что 1(п, п) = 1 для всех и > О. Если и > 1, то можно построить п циклов длины 1, т.е. 1-циклов. Очевидно, сделать это можно единственным образом, поскольку порядок записи цикла несущественен. Если и = О, то представляется разумным считать, что существует единственный способ построить цикл, не используя объекты, — просто не строить его.
Поэтому 1(п, и) = 1 для всех и > О. Далее необходимо показать, что Дп + 1, )с) = Дп, й — 1) + и~(п, й). Каждое размещение п+1 объектов сводится либо к размещению и+1-го объекта в новый цикл, либо к добавлению его в уже существующий цикл. Если и+ 1-ый объект размещен в новый цикл, то остальные и объектов размещены в )с — 1 циклах.
Последнее можно осуществить 1(п, й — 1) способами. Если и + 1-ый объект размещен в уже существующий цикл, содержащий, например, т объектов, то п+ 1-ый объект может быть помещен вслед за любым из т объектов в цикле. Следовательно, можно построить т различных циклов, если и+ 1-ый объект размешать в цикле, содержащем т объектов. Допустим, что имеются циклы с), сз, ..., сю где с, является п, циклом и пг + из + ..
+ иь = и. Тогда, если а„.ь) размещен в цикл с,, то можно построить и, новых циклов. Следовательно, путем добавления и+1-го элемента в фиксированное множество й-циклов, содержащих и элементов, можно образовать п1+пз+ +па = и новых циклов. Поскольку сушествуют 1(п, й) способов размещения и элементов в й-циклах, имеется и1(п, й) способов образовать й-цикл с и+ 1 объектами, если в цикл добавлен п+ 1-ый объект.
Следовательно, существуют 1 (п, й — 1) + п) ( п, й) способов разбиения и + 1 объектов по й-циклам и 1(п,й — 1) = з " . (е) Используя соотношение зь — — зь ) + пзь, можно построить таблицу (еэ1) (е) (е) чисел Стирлинга первого рода аналогично тому, как была построена таблица чисел Стирлинга второго рода. ТЕОРЕМА 12.6. Треугольник для чисел Стирлинга первого рода 494 ГЛАВА 72. Снова о комбинаторнык подсчетах ° УПРАЖНЕНИЯ Сколькими способами можно разместить 7 объектов в 3 ящиках, если а) объекты различимы, ящики различимы и ящики могут быть пустыми? б) объекты различимы, ящики различимы и ящики не могут быть пустыми? в) объекты неразличимы, ящики различимы и ящики могут быть пустыми? г) объекты неразличимы, ящики различимы и ящики не могут быть пустыми? д) объекты различимы, ящики неразличимы и ящики могут быть пустыми? е) объекты различимы, ящики неразличимы и ящики не могут быть пустыми? Сколькими способами можно разместить 10 объектов в 4 ящиках, если а) объекты различимы, ящики различимы и ящики могут быть пустыми? б) объекты различимы, ящики различимы и ящики не могут быть пустыми? в) объекты неразличимы, ящики различимы и ящики могут быть пустыми? г) объекты неразличимы, ящики различимы и ящики не могут быть пустыми? д) объекты различимы, ящики неразличимы и ящики могут быть пустыми? е) объекты различимы, ящики неразличимы и ящики не могут быть пустыми? Заполните следующие два ряда треугольника для чисел Стирлинга второго рода.
Заполните следующие два ряда треугольника для чисел Стирлинга первого рода. Сколькими способами можно разместить 12 объектов в 4 ящиках, если а) объекты различимы, ящики различимы и ящики могут быть пустыми? б) объекты различимы, ящики различимы и ящики не могут быть пустыми? в) объекты неразличимы, ящики различимы и ящики могут быть пустыми? г) объекты неразличимы, ящики различимы и ящики не могут быть пустыми? д) объекты различимы, ящики неразличимы и ящики могут быть пустыми? е) объекты различимы, ящики неразличимы и ящики не могут быть пустыми? 6. Сколькими способами можно разместить 14 объектов в 6 ящиках, если а) объекты различимы, ящики различимы и ящики могут быть пустыми? б) объекты различимы, ящики различимы и ящики не могут быть пустыми? в) объекты неразличимы, ящики различимы и ящики могут быть пустыми? г) объекты неразличимы, ящики различимы и ящики не могут быть пустыми? д) объекты различимы, ящики неразличимы и ящики могут быть пустыми? е) объекты различимы, ящики неразличимы и ящики не могут быть пустыми? РАЗДЕЛ 12.2.
Числа Каталана 496 7. Пусть Я(п,/с) = —, 2',, ( — 1)'~~,) (1г — 1)" а) Покажите, что Я(п, 0) = 0 для всех п > 1. б) Покажите, что Я(п, й) удовлетворяет рекурсивному отношению Я(п+1,/с) = Я(п,й — 1) + йБ(п,lс). 12.2. ЧИСЛА КАТАЛАНА В этом разделе рассмотрены три различные задачи, но в процессе их решения понятно, что это, по сути, одна и та же задача. 12.2.1 Задача 1 Человек идет на место работы, которое находится в десяти кварталах к северу и десяти кварталах к востоку от его дома. По диагонали, соединяющей его дом и место работы, течет река. К сожалению, на этом участке реки нет мостов, так что при достижении диагонали человек также достигает и реки.
Следовательно, он может попасть на диагональ, но после этого должен повернуть направо. Если улицы проходят по квадратной сетке, так, что в каждом квартале есть улицы в направлении север-юг и улицы в направлении восток-запад, то сколькими способами человек может попасть на работу, не возвращаясь и не пересекая реку. Примеры его возможных маршрутов показаны на рис. 12.1. Рис. 12.1 Если обозначить продвижение человека на один квартал на восток через Е, а его продвижение на один квартал на север через Х, то первый из приведенных маршрутов можно обозначить как ЕХЕЕХЕЕХХХЕЕЕЕХХХХЕХ. Второй маршрут можно обозначить как ЕХЕЕЕЕХХХХЕЕХХЕХЕХЕХ и третий — как ЕЕЕЕХХХХЕЕЕЕЕЕХХХХХХ.
Заметим, что любой маршрут должен начинаться с Е, и в любой точке маршрута количество продвижений Е должно быть не меньше количества продвижений Х, иначе человек попадет в реку. 496 ГЛАВА 12. Снова о комбинаторных подсчетах 12.2.2 Задача 2 Сколькими способами можно сложить последовательность из десяти чисел 1 и десяти чисел — 1 так, что если Яь — сумма первых и элементов последовательности, то Яь > 0 для всех 1 ( ?с ( 20.
Возможными последовательностями являются Заметим опять, что в любой точке вдоль любой из последовательностей количе- ство +1 должно быть не меньше количества — 1. 12.2.3 Задача 3 Задано 11 чисел и бинарные операции между ними. Сколькими способами в этом выражении можно вставить 10 пар круглых скобок? Эта проблема выглядит похожей на предыдущую, поскольку при движении слева направо закрывающих (правых) скобок должно быть не больше, чем открывающих (левых) скобок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
