Основы дискретной математики В.А. Осипова (552659), страница 18
Текст из файла (страница 18)
Формула включений и исключений применима к комбинаторной задаче, которая называется задачей о беспорядках. Имеется п различных предметов ал, аз, ..., а„и п различных ячеек бл, 52, ..., 5„. Сколькими способами можно разместить предметы по ячейкам так, чтобы никакой предмет ал не попал в ячейку бл? Рассмотрим всевозможные перестановки и символов (1, 2, ...
..., п). Из 3.1.2 следует, что их общее количество равно и!. С каждой перестановкой (гл, «2, ..., г„) этих символов свяжем матрицу которая называется подстановкой. Принято говорить, что подстановка к переводит элемент 1 в гл, элемент 2 в гз, ..., элемент п в г„и пишут к(?с) = гы Подстановка к такая, что для любого й = 1, ..., п к(й) ф «ь называется беспорядком. Например, при п = 3 беспорядками являются следующие подстановки: 321'231 Решение задачи о беспорядке дает следующее утверждение. Ъ'тверждение 3.5.
Число Р„подстановок на множестве из и символов, являющихся беспорядком равно На множестве всех перестановок п символов (1, 2, ..., п) рассмотрим свойства Гп Г2, ..., Г„, где Г;, г' = 1, ..., п — это свойство какой-либо подстановки оставлять символ г на месте. Тогда беспорядок — это такая подстановка, которая не обладает ни одним свойством Гл, Г, ..., Г„. Всего подстановок и!.
Число подстановок, обладающих свойством Гл равно (и — 1)!. Следовательно, общее число подстановок, которые обладают одним из свойств Гл, Г2, ..., Г„равно Сл,(п — 1)!. Число подстановок, обладающих свойствами Гл и Гз равно (и — 2)1, а всего подстановок, обладающих двумя свойствами равно Сз(п — 2)!. Аналогично, число подстановок, обладающих й свойствами, т. е. оставляющих на месте й символов равно Сс(п — ?с)1. По формуле (3.11).
Р„= п! — Сл (и — 1)1+ СС(п — 2)! — + ( — 1) С~с(п — ?с)1+ '+( — 1)"Сл 1! =и! (1 + — + + 1 1 1 ( — 1) 1 1! 2! 3! и.' и!' Замечание. При и » оо Ра — » —, т. е. число е и!' беспорядков Р„аппроксимируется числом —. е 3.2.2. Рекуррентные соотношения и производящие функции Для решения ряда комбинаторных задач о подсчете числа объектов используют метод сведения данной задачи к задаче с 100 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ 101 3.2.
Некоторые методы пересчета меньшим числом объектов. При этом пользуются выражением, связывающим число объектов с заданным свойством, зависящим от некоторого целого неотрицательного параметра п, с числом объектов, зависящим от предыдущих значений параметра, например, п — 1, п — 2. Такие соотношения называются рекуррентными (от латинского гесштепв — возвращающийся). Точнее, рекуррентным соотношением называется соотношение вида ап ~я — — г'(п, а„, аа+м ..., ап+р 1), которое позволяет вычислить любой член последовательности, если заданы ее первые р членов. Примеры рекуррентных соотношений: а) а„+1 = с?а„(д ф 0) — геометрическая прогрессия; б) а„ь1 = а„+ с1 — арифметическая прогрессия; в) а +2 = а ьт + а„— рекуррентное соотношение для последовательности Фибоначчи.
Положим а1 = 1, аз = 1. Тогда ав = 1 + 1 = 2, а4 = 1 + 2 = 3 и это рекуррентное соотношение определяет последовательность чисел 1, 1, 2, 3, 5, 8, ..., называемых числами Фибоначчи. С помощью рекуррентного соотношения, и зная решение задачи для небольшого числа объектов (сколько — зависит от задачи), можно определить число объектов с заданным свойством для любого п. Пример 3.9. Итальянский математик Фибоначчи в 1228 году привел следующую задачу. Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорохсденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов? Обозначим через г'(п) количество пар кроликов, которые появятся по истечении п месяцев с начала года. Тогда по условию г'(0) = О, Г(1) = 2.
Через (п + 1) месяц у нас будут г (п) пар и еще столько новорожденных пар, сколько было в конце (п — 1) месяца, т. е. Р(п+ 1) = Г(п) + Р"(п — 1). Это рекуррентное соотношение определяет последовательность Фибоначчи. Приведем примеры известных рекуррентных соотношений, связа,нных с комбинаторными задачами. Обозначим через В„число различных разбиений множества, состоящего из п > 1 элементов. Эти числа называются числами Белла.
Положим Во = 1. Тогда числа Белла удовлетворяют рекуррентному соотношению В .а1 = СоВо + С1В1 + .. + С' В, п > О. Обозначим через $(п, к) число разбиений п элементного множества на а непустых подмножеств (а < п). По определению положим $(0, 0) = 1, $(0, ги) = О, если т ~ О, $(п, 1с) = О, если п > 0 и й ф (1, 2, ..., п). Числа $(п, к.) называют 'числами Стирлинга 2 рода Для них выполняется рекуррентное соотношение: $(п, Й) = Й$(п — 1, Й) + $(п — 1, Й вЂ” 1), п > 1. Можно доказать, что имеет место представление 1 ~т- п~ т1 тте "т ' ' '+та=а Говорят, что числовая последовательность ао,ам ..., а„, ... является решением данного числового соотношения, если при подстановке этой последовательности рекуррентное соотношение тождественно выполняется. Например, члены арифметической прогрессии О, 2, 4, б, ...
являются решением рекуррентного соотношения ап+1 = а„+ 2, ао = О. Для решения рекуррентных соотношений общих правил, вообще говоря, нет. Один из способов их решения связан с использовйнием метода производящих функций. Производящей функцией последовательности чисел ав, ам ... ..., а„, ... называется степенной ряд А(1) = ав+а1Д+а21~+ .. +а„1" + в предположении, что он сходится в каком-нибудь интервале !~! < ге Например, производящей функцией последовательности 1, 1, ..., 1, ..., т. е.
такой, что а„= 1, п = О, 1, ... является функция 1 2 1 — 1 =1+~+~ + +с" + Глава 4 Задачи и упражнения 102 Глава 3. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ Производящей функцией конечной последовательности чисел аь = С~~, й = О, 1, ..., и является (1+ ~)" = Со+ С11+ . + С~",'1" + . + С„"~", (3.12) как следует из формулы бинома Ньютона (3.5) при а = 1, 6 = 1. С помощью производящей функции можно выводить различные свойства чисел С„, в том числе, полученные ранее ь другим способом. Например, положив в (3.12) 1 = 1, получим соотношение: и ~~) С~ = 2". в=о Метод производящих функций используется в комбинаторике для решения большого класса сложных задач пересчета, для решения рекуррентных соотношений. 1. Подсчитать, сколько останется чисел в первой сотне, если вычеркнуть все числа, делящиеся на 2, 3 и 5.
2. Определить число целочисленных решений системы х1 + хэ + хз = 20, 1 ( хэ ( 9, О ( хэ ~ (9, 0 ( хз ( 9. 3. Подсчитать число беспорядков Ов. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Теория графов — раздел дискретной математики, имеющий многочисленные приложения в различных областях экономики, социологии, техники. Теория графов «открывалась» независимо много раз. Наиболее раннее известное упоминание этой теории встречается в работах Л.
Эйлера, хотя проблему, которой он занимался можно рассматривать как обычную головоломку. Затем Г. Кирхгоф, занимаясь изучением электрических цепей, и А. Кали, рассматривая проблему перечисления изомеров в органической химии, вновь подошли к решению задач теории графов. С тех пор многие исследователи, формируя модели в своих предметных областях, приходили к описанию их с помощью теории графов.
Сам термин «граф» впервые был введен в 1936 году Д. Кенигом. Методы теории графов успешно применяются в современной прикладной науке в задачах управления производством, при проектировании различных физических систем, являются основой математического обеспечения систем обработки информации. Теоретико-графовый подход используется в линейном программировании и исследовании операций, сетевом планировании и управлении. Теория графов тесно связана со многими разделами современной математики, содержит много интересных проблем, не решенных до настоящего времени. 4.1. Ориентированные и неориентированные графы.
Основные понятия. Примеры приложений теории графов Говорят, что задан ориентпированный граф С =( Р; Г ), если указаны два множества: непустое множество г' и множество Г упорядоченных пар ( о, у >, где и, д е Ъ'. Элементы 105 4.1. Ориентированные и неориентированные графы 104 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ множества T называют вершинал4и графа С, упорядоченные пары < и, у > — дргалли графа. Граф можно изобразить на плоскости, ставя в соответствие каждой вершине и точку, а каждой дуге < и, у > — линию со стрелкой, соединяюшую эти точки.
Пример 4.1. На рнс. 4.1 приведены два изображения ориентированного графа С =< 1', Г ), где 1' = (и1, из, из, и4) и51, Г = (< и1) 62 ), < и1) из )) < из) и2 >) < из) и5 >)< и5) и1 >) < и5, и2 >, < из) из >1. Поскольку множество упорядоченных пар Г есть ни что иное, как бинарное отношение на множестве Ъ', то часто говорят, что граф изображает некоторое бинарное отношение, и бинарные отношения на конечных множествах иллюстрируются такими рисунками. Граф может служить моделью для всякой системы, содержащей бинарное отношение.
Рис. 4.1. Наряду с понятием ориентированного графа исгюльзуют также понятие неориентированного графа. Говорят, что задан пеориептироваппый граф С =< 1', Я >, если указаны два множества: непустое множество 'и' и множество Я некоторых пар (и, у1 элементов из Ъ'. Элементы множества и' называют вершинами графа С =< 1г, Я >, неупорядоченные пары (и, у1 — ребрами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
