Шапорев С.Д. Дискретная математика - файл n3.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n3.doc





§ 2.3. Применение производящих функций для получения

комбинаторных чисел.
Применим теорию производящих функций и получим явные выражения чисел Фибоначчи. Числа Фибоначчи есть число способов расположить знаков, из которых каждый нуль или единица, в последовательность, не содержащую двух нулей подряд. Эта последовательность задается рекуррентной формулой

(2.3.1)

Рассмотрим производящую функцию последовательности чисел Фибоначчи Умножим рекуррентное уравнение в формуле (2.3.1) на и просуммируем полученное выражение от двух до бесконечности. Два числа и известны из начальных данных, поэтому необходимо сбросить индексы и В результате получим уравнение

Так как

, то

Аналогично Тогда или Окончательно производящая функция последовательности чисел Фибоначчи равна

(2.3.2)

Так как обычный степенной ряд, представляющий производящую функцию, есть ряд Тейлора в окрестности точки , то полученное выражение можно разложить по общему правилу в ряд Тейлора и получить формулу общего члена При этом выгоднее использовать замены переменных и уже существующие разложения функций в степенные ряды. Поступим именно таким образом. Разложим дробь на простые слагаемые, для чего найдем сначала корни знаменателя. Тогда

Те-



Леонардо Фибоначчи (Пизанский) (1180-1240 г.г.) - итальянский математик.

Брук Тейлор (1685-1731 г.г.) - английский математик.

перь воспользуемся известным разложением Итак, ; . Тогда . Точно таким же образом . Теперь можно записать разложение исходной дроби Умножим полученное выражение на , тогда

. Поэтому коэффициент при в разложении будет иметь вид Упростим эту формулу, подставив числовые значения



Отсюда






Итак, окончательно (2.3.3)
§ 2.4. Экспоненциальные производящие функции.
Они соответствуют упорядоченным - выборкам или - перестановкам. Из определения упорядоченных и неупорядоченных - выборок ясно, что первых в раз больше чем вторых. Поэтому производящая функция в этом случае записывается

в виде (2.4.1)

где - число - перестановок из элементов, то есть в принятых обозначениях.

В случаях когда допускаются повторения элементов необходимо в левой части формулы (2.4.1) биномы заменить на соответствующие многочлены вида если никакие ограничения на повторные появления не наложены, или многочлены вида , если соответствующий элемент допускает повторений в выборках. Представление этого произведения в виде ряда по степеням дает в качестве коэффициентов при числа - перестановок, допускающих указанные выше повторения.

Название экспоненциальная применяется в силу того, что производящая функция для - перестановок с неограниченным числом повторений из элементов имеет вид (2.4.2)

Так как производящие функции (и простая и экспоненциальная) представляют собой степенной ряд, то в области его сходимости этот ряд можно почленно дифференцировать и интегрировать и, следовательно, получать новые степенные ряды и новые производящие функции. Например, возьмем Почленным интегрированием этого ряда в области получаем выражение для производящей функции (2.4.3)

то есть
§ 2.5. О приложениях теории производящих функций к

теории вероятностей.
Исторически сложилось так, что прежде всего комбинаторные методы нашли применение в теории вероятностей и математической статистике. В современной аксиоматической теории вероятностей сами вероятности мыслятся лишь в связи с пространствами элементарных событий. Комбинаторные методы находят себе место в теории вероятностей именно в той ее части, когда пространства элементарных событий дискретны. Можно даже говорить о теоретико - вероятностных интерпретациях определенной части комбинаторного анализа.

В самом деле - выборки могут быть интерпретированы различными урновыми схемами. Случаи, когда допускаются повторения элементов в выборках, соответствуют урновым схемам с возвращением. Одна из простейших производящих функций в теории вероятностей связана с бросанием монеты и другими событиями с двумя исходами: Для независимых испытаний с двумя исходами (схема Бернулли) производящей функцией будет

Производящая функция бросания одной шестигранной кости с равновероятными выпадениями очков имеет вид:



Комбинаторные задачи о размещениях в их теоретико - вероятностной трактовке приводят к введению различных моментов и функций накопления. Это также верно и для теоретико - числовых интерпретаций и для задач технической автоматики.
Глава 3. Метод включений и исключений.
Содержание комбинаторного анализа не исчерпывается подсчетом числа решений соответствующих задач. Не менее важное место в нем занимают проблемы возможности или невозможности осуществления требуемых выборок или расположений элементов. Логическая сущность метода включения и исключения определяется тем, что он применяется к важной задаче разделения множеств на подмножества в зависимости от того, обладают ли их элементы определенной совокупностью свойств или нет.
§ 3.1. Подсчет числа элементов объединения множеств.
Рассмотрим сначала простую задачу о нахождении числа элементов суммы множеств. Будем обозначать через количество элементов множества Основная формула, которой пользуются при нахождении числа элементов суммы двух множеств такова: (3.1.1)

Эта формула совершенно очевидна из диаграммы Эйлера - Венна. С помощью формулы

(3.1.1) можно получить формулу для числа

элементов объединения любого числа мно-

жеств. Например, для трех элементов имеем

















Эту формулу

тоже еще можно изобразить с помощью ди-

аграммы. Для случая слагаемых анало-

гичная формула доказывается методом математической индукции.



Яков Бернулли (1654-1705 г.г.) - швейцарский математик.
Теорема 1. Если - некоторые множества и , то



(3.1.2)

Формулу (3.1.2) можно обобщить и подсчитывать не только количество элементов данных множеств. Пусть дано - множество некоторых элементов и - множество свойств: , которыми элементы множества могут как обладать, так и не обладать. Выделим какую-либо - выборку свойств

Число элементов , обладающих всеми выбранными свойствами обозначим через Отсутствие у элемента какого-либо свойства будем обозначать . Тогда, например, запись означает число элементов, обладающих свойствами и и не обладающих свойством .

а). Пусть имеется одно свойство , тогда

б). Имеется конечное число свойств , несовместимых друг с другом. Тогда опять

в). Элементы обладают комбинациями различных свойств. Тогда справедлива теорема, аналогичная теореме 1.

Теорема 2. Если даны - множество элементов и - множество свойств совместимых между собой, тогда



(3.1.3)

Доказательство.

Теорема может быть доказана с помощью простейших рассуждений, состоящих в попеременном отбрасывании и возвращении подмножеств. Применим, однако, метод математической индукции.

. Эта формула очевидна. Пусть теорема верна для свойств, то есть

(3.1.4)

Перейдем к случаю, когда имеется свойств. Так как , то по аналогии можно написать Применим соотношение (3.1.4) для числа Получим формулу (3.1.5)

Прокомментируем эту формулу. В ней - число элементов, обладающих свойством и одновременно не обладающих свойствами ; - число элементов, обладающих только свойством . - число элементов, обладающих свойствами одновременно и так далее. Ясно, что для того чтобы получить из общего числа элементов со свойством надо вычесть сначала число элементов, обладающих свойствами . Однако при этом элементы, имеющие три свойства: именно и, скажем, будут исключены дважды (сначала как элементы со свойствами , затем как элементы со свойствами ). Значит надо возвратить все элементы, обладающие тремя свойствами, то есть прибавить и так далее.

Вычтем теперь из (3.1.4) формулу (3.1.5), получим



Характер доказательства этой теоремы таков, что его можно применить для любой комбинации свойств, как выполняющихся, так и не имеющих места. Таким образом, в левой части доказанной формулы может стоять не только , но и, например, Теорема формулируется при этом относительно совокупности свойств с обязательным выполнением свойств следующим образом: (3.1.6)

Пример. В комнате несколько человек, знающих хотя бы один из трех языков. Шестеро знают английский, шестеро - немецкий, семеро - французский. Четверо знают английский и немецкий, трое - немецкий и французский, двое - французский и английский. Один человек знает все три языка. Сколько человек в комнате? Сколько из них знают только английский язык?

Задачу можно решить традиционным способом «вычерпывания» множеств без применения формулу включений и исключений. Перепишем условие задачи более компактно в виде таблицы


А

Н

Ф

АН

НФ

ФА

АНФ

6

6

7

4

3

2

1


Пусть из комнаты ушел человек, знающий все три языка, тогда получим


А

Н

Ф

АН

НФ

ФА

АНФ

5

5

6

3

2

1

0


Пусть теперь ушли три человека (из оставшихся), знающие одновременно английский и немецкий языки; число людей, знающих другие пары языков, не изменится.


А

Н

Ф

АН

НФ

ФА

АНФ

2

2

6

0

2

1

0


Пусть уйдут двое, знающих немецкий и французский.


А

Н

Ф

АН

НФ

ФА

АНФ

2

0

4

0

0

1

0


Наконец, уходит человек, знающий французский и английский языки. Окончательно получим

А

Н

Ф

АН

НФ

ФА

АНФ

1

0

3

0

0

0

0


Итак, в комнате остался один человек, знающий только английский язык, и трое, знающих только французский язык. Кроме того вышло семь человек, значит сначала в комнате было одиннадцать человек.

Решим теперь эту же задачу методом включений и исключений. Пусть свойство - знать английский язык, аналогично и - свойства, характеризующие знание немецкого и французского языков. По условию задачи общее число людей составляют все, знающие хотя бы один язык; не знающих хотя бы один язык в задаче нет. По формуле (3.1.2) имеем



Число людей, знающих только английский язык это . По формуле (3.1.6) Так же легко может быть найдет ответ и на другие подобные вопросы.
§ 3.2. Учет весов элементов в формуле включения и исключения.
Дальнейшие усложнения метода связаны с введением весов элементов. Как и прежде, будем считать, что веса это числовые характеристики элементов рассматриваемых множеств.

Итак, пусть задано - множество и каждому элементу приписан вес из - множества свойств . Произведем - выборку свойств и обозначим сумму весов элементов, обладающих всеми выбранными свойствами, через Сумму, распространенную на все возможные - выборки свойств, обозначим Через обозначим сумму весов всех элементов множества . При таких обозначениях теорема включений и исключений с учетом весов будет формулироваться следующим образом.

Теорема 3. Если даны - множество , каждый элемент которого имеет вес, и - множества свойств, то сумма весов элементов, не удовлетворяющих ни одному из заданных свойств, определяется по формуле:

(3.2.1)

Итак, сумма весов множества из элементов, не удовлетворяющих ни одному из свойств, равна сумме весов всех элементов множества минус сумма весов элементов, обладающих хотя бы одним свойством, плюс сумма весов элементов, имеющих не менее двух свойств и так далее. Перечислим еще раз все используемые обозначения.

Здесь - сумма весов элементов, обладающих всеми выбранными свойствами; - сумма весов во всех возможных - выборках из свойств элементов, обладающих не менее чем выбранными свойствами. Если элементу принадлежат свойств, то он в этой сумме будет учитываться раз. В самом деле, всякий элемент , если он имеет свойств, вносит свой вес в первое слагаемое один раз, во второе раз, в третье раз и так далее, а всего раз. - сумма весов всех элементов множества , - сумма весов всех элементов, обладающих хотя бы одним свойством, - сумма весов всех элементов, обладающих не менее чем двумя свойствами, - сумма весов всех элементов, обладающих не менее чем свойствами, - сумма весов элементов, не обладающих ни одним из указанных свойств.

Если все элементы имеют единичный вес, то и сумма весов равна числу слагаемых в сумме. В этом случае , равно числу элементов множества , не удовлетворяющих ни одному из указанных свойств. Тогда формула (3.2.1) переходит в формулу

(3.2.2)

Можно посчитать и сумму весов элементов, обладающих ровно указанными свойствами. Об этом идет речь в следующей теореме.

Теорема 4. Сумма весов элементов - множество , удовлетворяющих - выборке из - множества свойств , находится по формуле



(3.2.3)

Здесь - сумма весов элементов с учетом их кратности, обладающих не менее чем свойствами, - сумма весов элементов, обладающих ровно свойствами. Так как , то



(3.2.4)

Если опять , то есть , то формула (3.2.4) превращается в

(3.2.5)

Метод включения и исключения применяется везде, где речь идет о разделении дискретных множеств, производимых в зависимости от наличия (или отсутствия) у элементов определенных свойств. К числу задач, решаемых с помощью этого метода, относятся, например, задачи о встречах или беспорядках, разновидности задач теории чисел и ее приложений, где применяются специальные функции Эйлера и Мебиуса.

Пример 1. Задача о беспорядках или задача о встречах.

Пусть имеется конечное упорядоченное множество чисел Для них могут быть образованы перестановки . Число всех перестановок, очевидно, . Среди этих перестановок имеются такие, где ни один из элементов не сохранил своего первоначального места: Такие перестановки называются беспорядками. Найдем число беспорядков.

Множество элементов рассматривается по отношению к множеству свойств элементов оставаться на своих местах Очевидно, что если элементов закрепляются на своих местах, то число соответствующих перестановок равно Число способов, которыми можно выбрать закрепленных элементов из общего количества элементов равно Число беспорядков тогда находится по формуле, аналогичной формуле (3.2.1)

(3.2.6)

Здесь выражение обозначает целую часть заданного числа, а - основание натуральных логарифмов.

Пример 2. Задача о числе перестановок, в которых остаются на своих

местах элементов.

В этой задаче из элементов должно быть неподвижных. Число способов, которыми можно выбрать эти неподвижных элементов равно Оставшиеся элементов могут образовывать беспорядки, их число подсчитаем по формуле (3.2.6). Тогда по правилу произведения



(3.2.7)

§ 3.3. Функция Эйлера.
Функцией Эйлера называется функция , определенная на множестве , значения которой равны числу натуральных может быть и составных целых чисел, взаимно простых с и не превосходящих , то есть

Знаком обозначается наибольший общий делитель натуральных чисел



Мебиус (1-1 г.г.) - ский математик.

и . Взаимно простыми называются числа, наибольший общий делитель которых равен единице. Например, натуральные числа 5 и 7 взаимно просты, так как Таким образом, взаимно простые числа друг на друга нацело не делятся.

Функция Эйлера аналитически выражается следующим образом

(3.3.1)

где - есть число простых делителей числа Чаще функция Эйлера приводится в несколько другом виде

(3.3.2)

Формулы (3.3.1) и (3.3.2) получим позже, а сейчас посчитаем значения для Разложим числа с 1 до 10 на простые делители.






















1). . Нет числа, не превосходящего единицу и взаимно простого с единицей.

2). . Это число 1.

3). . Два числа не превосходят 3 и взаимно просты с числом 3; это числа 1 и 2.

4). . Это числа 1 и 3.

5). . Четыре числа удовлетворяют условию существования функции Эйлера. Это числа 1, 2, 3 и 4.

6). . Это числа 1 и 5.

7).

. Значение функции Эйлера в этом случае равно шести, так как шесть чисел удовлетворяют условию существования функции Эйлера. Это числа 1, 2, 3, 4, 5 и 6.

8). . Значение функции Эйлера равно четырем. Это числа 1, 3, 5 и 7.

9).

. Это числа 1, 2, 4, 5, 7 и 8.

10). . Это числа 1, 3, 7 и 9.

Таким образом, функция Эйлера для первых десяти значений аргумента может быть задана следующей таблицей.




1

2

3

4

5

6

7

8

9

10



0

1

2

2

4

2

6

4

6

4


Выведем теперь формулы, представляющие функцию Эйлера. Для этого решим сначала такую вспомогательную задачу. Пусть - взаимно простые натуральные числа, то есть - некоторое натуральное число. Найдем число натуральных чисел, не превышающих и не делящихся ни на одно из чисел . Пусть - множество натуральных чисел, не превышающих и делящихся на Тогда количество чисел, делящихся по крайней мере на одно из чисел равно

Очевидно , где опять - наибольшая целая часть , не превосходящая . Множество - это множество тех чисел, которые делятся на , то есть , поскольку числа взаимно простые. По формуле (3.1.2) получим



Тогда количество чисел, не превышающих и делящихся по крайней мере на одно из чисел равно



Количество чисел, не превышающих и не делящихся ни на одно из чисел равно Эта формула аналогично формуле (3.1.4) и представляет собой по сути формулу включений и исключений. Ее можно было сразу написать, если ввести - свойство числа делиться на Тогда - количество чисел не превосходящих и обладающих свойством Пусть теперь - натуральное число, разложение которого на простые множители имеет вид , где - простые числа. Если - число натуральных целых чисел, взаимно простых с , то по только что полученной формуле имеем



Преобразования сумм в произведения очень громоздки и связаны с разложением многочлена на множители. Например, для соответствующие преобразования будут иметь вид

Пример. Найти число способов разложения шаров по ящикам так, чтобы ящиков остались пустыми.

Рассмотрим простейший пример. Пусть Из рисунка сразу

1-й ящик 2-й ящик 3-й ящик ясно, что порядок, то есть но-

мер шаров важен, следователь-

1234 5 но речь идет о - перестанов-

1235 пуст 4 ках. В данном опыте выбирает-

1245 3 ся ящик. Это выборка с повто-

рениями, так как ящики могут

повторяться, например, первый шар положен в первый ящик, второй шар положен в первый ящик и так далее. На основе такого простого примера ясно, что речь идет о выборке ящиков раз ( шаров) с повторениями. Таким образом, число способов, которыми можно разместить шаров по ящикам равно

Пусть свойство, состоящее в том, что при данной раскладке ящик с номером остался пустым. Тогда количество раскладок, обладающих свойствами при одном способе выбора пустых ящиков равно , а общее количество раскладок, распространенное на все возможные способы выбора пустых ящиков, будет равно .

Применим теперь формулу включений и исключений типа (3.2.5), получим





.

§ 2.3. Применение производящих функций для получения
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации