Дискретная математика (998286), страница 27
Текст из файла (страница 27)
подраздел 1.7А). Таким образом, число различных ядер сюрьективных функций — это число Стирлинга второго рода Я(т, и). Всего сюръекгивных функций в(т,п) = Ы Я(т,п), так как число сюръективных функций с Ьадаиным ядром равно числу перестановок множества значений функции. 151 6,6. Принцип еключеиия и исключения Тогда З = ).) Зв, где Зв.=1Х 6 З ~ В ~ Х), Пусть В Е В и Ь = ~В~ Тогда Вев 1Зв! = В(т+ 1 — Ь). Заметим, что !1В 6 В ~в) = Ь) ~ = С(т,ь 1). Следова. тельно, В1 +ц=~З~= ~ ~С(т,Ь-1)В~ — Ь+1)= Ь=1 с ю С(т,т — 1)В(г) = ~ С(т,т)ВЯ, где 1= тп — Ь+1 5.5. Принцип включения и исключения Приведенные в предыдущих четырех разделах формулы и алгоритмы дают способы вычисления комбинаторных чисел для некоторых распространенных комбинаторных конфигураций.
Практические задачи не всегда прямо сводятся к известным комбинаторным конфигурациям. В этом случае используются различные методы сведения одних комбннаторных конфигураций к другим. В этом и двух следующих разделах рассматриваются три наиболее часто используемых метода. Мы начинаем с самого простого и прямолинейного, но имеющего ограниченную сферу применения принципа включения н исключения. 5.5.1.
Объединение конфигураций Часто комбинаторная конфигурация является объединением других, число комбинаций в которых вычислить проще. В таком случае требуется уметь вычислять число комбинаций в объединении. В простых случаях формулы для вычисления очевидны; )АОВ~ = )А~+ ~В~ — )АПВ), ~А ~1 В О С! = )А) + ~В! + ~С~ — ~А П В~ — )В п С! — ~А П С! + !А П В и С!. Пример Сколько существует натуральных чисел, меньших 1000, которые не делятся нн на 3, ни на 5, ни на 77 Всего чисел, меньших тысячи, 999. Из них: ь 999; 3 = ЗЗЗ делятся на 3, ь 999: 6 = 199 делятся на 5, ь 999: 7 = 142 делятся на 7, ~ 999; (3 * 6) = 66 лелятся на 3 н на 5, ~ 999: (3 е 7) = 47 делятся на 3 и на 7, 147 э:3: Бииомиальные коэффициенты 1 1 1 1 2 1 з з 1 4 6 4 1 В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой.
двух чисел, стоящих над ним. Число сочетаний С(т, и) находится в (го+ 1)-м ряду на [и + 1)-м месте. 5.3.5. Генерация подмножеств Элементы множества (1,...,|и) упорядочены. Поэтому каждое и-элементное подмножество также можно рассматривать как упорядоченную последовательность. На множестве таких последовательностей естественным образом определяется лексикографический порядок (см. упражнение 1.8). Следующий простой алгоритм генерирует все и-элементные подмножества ги-элементного множества в лексикографическом порядке. Алгоритм 6.3.
Генерация и-элементных подмножеств т-элемеитного множества Вход: и — мощность подмножества, т — мощность множества, т > и > О. Выход: последовательность всех и-элементных подмножеств т-элементного множества в лексикографическом порядке. Гог | 6'оп| 1 Го т г]о А[1] | = | ( инициализация исходного множества ) ел|1 Гог 1Г т = и гЬеп у|еЫ А[1..и] ( единственное подмножество ) ехв епд |Г р: = и ( р — номер первого изменяемого элемента ) «Ьйе р> 1 но у1е14 А[1.т] ( очередное подмножество в первых и элементах массива А ) 1Г А[и) = и| тЬеп р: =р — 1 ( нельзя увеличить последний элемент ) е1ве р: = и ( можно увеличить последний элемент ) епд 1Г |Г р > 1 ГЬеп Гог | бои| и огивппг р г[о А[1]: = А[р] + | — р+ 1 ( увеличение элементов ) епд Гог епд 1Г епо «Ьйе 5.6.
Формулы обращения 153 /«-1 «-1 = ~~~) (А;~+~А !) — ~ ~~А;пА,)+~~ )АпА„~ +,, я=1 1<я<уй«-1 «=1 -(-1)"-'~А,п" пА„,пА„~= (А,~ — ~ ~)АпА,)+ . +(-1)" '!А,п пА„~. я=1 1<я<у<« 5.5.3. Число булевых функций, существенно зависящих от всех своих переменных Р„=~Р„~(Р„'и" ОР„")~= Р„~ Ц Р„*. «=1 С другой стороны, ~Р„'~ = 2э, более того, ~Р„' и. -пР„"~ = 2а . Следовательно, 2~ — Ч~ (Р„*( — ') ~Р„'ПР„'~+" +( — 1)" "~Р„'П ПР„"! ~=1 1<Я<1«« 2~ — (С(п,1)2 — С(п,2)2~ +" +( — 1)" ~С(п,п)2) = « ( — 1) 'С(п, 1) 2э Р« = 5.6. Формулы обращения Очень полезную, но специфическую группу приемов образуют различные спосо- бы преобразования уже полученных комбинаторных выражений.
В этом разделе рассматривается один частный, но важный случай. 5.6.1. Теорема обращения Пусть а„л и Ь„ь — некоторые (комбинаторные) числа, зависящие от параметров и и Ь, причем О < Ь < и. Если известно выражение чисел а„,ь через числа Ь„,ь то в некоторых случаях можно найти н выражение чисел Ь„ь через числа а„л то есть решить комбинаторное уравнение. Рассмотрим применение принципа включения и исключения на примере следующей задачи. Пусть р„: = ~Р„~ = 2э — число всех булевых функций и переменных, а р„— число булевых функций, существенно зависящих от всех п переменных (см. подраздел 3.1.2). Пусть Р„' — множество булевых функций, у которых переменная ач фиктивная (кроме к; могут быть и другие фиктивные переменные), Имеем: 154 Глава 5.
Комбинаторика ТЕОРЕМА Пусть Ып Ый < и а„„= ~~» Ли „,Ьи,. и пусть и, 31г,й,; ЫЬ < и Ыт < и ~ ~р„й ОЛ„, а=о ~о Тогда и ЫЬ<пЬ й=~~ и й;а а=в ДОКАЗАТЕЛЬСТВО и и / аа Е Ип,й,аои,а Х~~ Рп,й,а Х~~ Лп г аиЬп па а=в а=о ап=в гап,й,аЛп,атпа Ьи,иа Ьп йа. аи=в айаив 5.6.2. Формулы обращения для биномиальных коэффициентов ЛЕММА ~~ ( — 1)' С(п,т)С(т,т) = (О, т<п. Доклз Атал ьство п ( — 1)' С(та, т)С(т, т) ~ ~( — 1)*- С(п,т)С(п — т,а-т) = а=в и ( — 1)' С(п,т)С(п — т,т — т) = а=в п С(п, т) ~~а ( — 1)* С(п — т, т — т).
Но при т < и имеем: ~ ( — 1)' С(п — т, т — т) = ~~а (-1)АС(п — т,,у) = О, г О Применение теоремы обращения предполагает отыскание для заданных чисел Ли й; (коэффициентов комбинаторного уравнения) соответствующих чисел га„й,„ удовлетворяющих условию теоремы обращения. Особенно часто числами Ли,й; являются биномиальные коэффициенты. 155 5.6.
Формулы обращения где 1': =1 — т. С другой стороны, при т = и имеем: С(п,т) ~~~ ( — 1)' С(о — т,1 — т) = С(о,о)( — 1)" "С(0,0) = 1. д ТЕОРЕМА Если а ь = ~, 'С(й,т)Ь„А, то Ь„ьь = ) ( — 1)ь 'С(й,г)а Доказатвпьство Здесь Лмь1 = С(й т) и 1ь ь ф — ( — 1)~ ~С(й,т). При й ( и т ( и имеем п Е ..
р„,,лЛ„„, и ( — 1)~ 'С(й,й)С(ю',т) = в=о ~~',( — 1) '+ ~С(й,1)С(1, т) = ~=о ь ( — 1) ~ ( — 1)' ~С(й,в)С(1,т) = 1=о 1, й=т, О, йфт. 1=0 ТЕОРЕМА Есла а„,ь = ~ , 'С(т, й)Ь„;, то Ь ь = ~ ( — 1)а-ьС(1, й)а„,. Доказательство здесь л да = с(1 ") и ать; = ( — 1)' "с(т,й). при й (и, т ( о имеем: И и ~,Рп,м1Лл...о, = ~~ (-1)' ~С(1,й)С(т,1) = *=о а=о ( — 1)' ~С(т,1)С(т,й) = 1, й=и, О, йфа. 5.6.3. Формулы для чисел Стирлинга В качестве примера использования формул обращения рассмотрим получение явных формул лля чисел Стирлинга первого и второго рода.
Рассмотрим множество функций У; А -~ В, где )А! = и и ~В) = й. Число всех таких функций равно й". С другой стороны, число функций Л таких что Ьг"(А)! = й равно о(т, о), Глава 5. Комби»етоиихо 156 поскольку в(», и) — это число сюръективиъ»х функций Г'. 1..п -» 1.л. Но область эиачеиий функции (при заданном 1) можно выбрать С(й, г) способами. Поэтому 1" = Х С(к,$)8(1,б). ~=о Обозначив а„ь: = к" и Ь„,: = в(1, и), имеем по первои теореме предыдушего под- раздела, в(а,п) = ~~ ( — 1) 'С(»,й)1". ~=о Учитывая связь чисел Стирлиига первого и второго рода, имеем: 1 Я(а,п) = —,~~ (-1)" 'С(»,к)»". »=о 5.?. Производящие функции Для решения комбииаториых задач в некоторых случаях можно использовать методы математического анализа.
Разиообразие применяемых здесь приемов весьма велико, и ие может быть в полном объеме рассмотрено в рамках этой книги. В данном разделе рассматривается только осиовиая идея метода производящих функций, применение которой иллюстрируется простым примером. Более детальиое рассмотрение можно найти в литературе, например в (20]. 5.7.1. Основная идея Пусть есть последовательность комбииаториых чисел а; и последовательность функций р,(х).
Рассмотрим формальный ряд: з(х): = ~~» а;»р;(х). о.(х) называется лроизводяшрй фуи»а1ией (для заданной последовательности комбииаториых чисел а; относительно заданной последовательности функций р;(х)). Обычно используют»р;(х): = х*' или р,(х): = х'/»». Пример Иэ формулы бинома Ньютона при у: = 1 имеем: (1+ х)" = ~~» С(п, г)х'. ~о Таким образом, (1+ х)" является производящей функцией для бииомиальиых коэффициентов. 157 Упражнения 5.7.2. Метод неопределенных коэффициентов Из математического анализа известно, что если У(х): = ~~~ а;чч(х) и 9'(х): = У б,~р;(х), то ч2' а; = О; (для рассматриваемых здесь систем функций 22;).
В качестве примера применения производящих функций рассмотрим доказательство следующего тождества. ТЕОРЕМА С(2п, п) = ~~~ С(п, й)2. ДОКАЗАТЕЛЬСТВО Имеем: (1+ х)2" = (1+ х)" (1+ х)". Следовательно, 2« « » 'У С(2, ) ' = Х 'С(, )*' ~С(п, )х*. 4=О 2=0 в=О Приравняем коэффициент при х": « С(2п, п) = ~> С(п, й) С(п, п — й) = ~~~ С(п, й)2. Комментарии Сведения из области комбинаторного анализа в том или ином обьеме приводятся в любом учебнике по дискретной математике (см., например, [25, 18]).
Явные формулы для комбинаторных чисел часто используются при оценке размера пространства поиска в переборных задачах программирования. Очень богатый набор полезных формул-для комбинаторных чисел можно найти в книгах [19] и [20]. Все алгоритмы этой главы заимствованы (в модифицированном виде) из книги [14]. Упражнения 5.1. Доказать, что А(гп, п) = А(п2 — 1, п) + пА(тп — 1, п — 1). 5.2. Доказать, что множество перестановок с четным числом инверсий образует группу. 5.3. Доказать, что птс(тп — 1, п — 1) = пс(т, и).
5А. Доказать, что число последовательностей длины и, составленных из элементов множества 1..т и содержащих каждый элемент множества 1..гп по крайней мере один раз, равно т|З'(и, гп). 188 Глава б. Комбинаторика 5,5, Рассмотрим множество функций 1: Х -+ Х, где ~Х~ = и. Элемент х Е Х называется неподвижной точкой функции 1, если Дх) = х. Пусть ̈́— множество функций, не имеющих неподвижных точек. Определить, чему равно (Н„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
