Шапорев С.Д. Дискретная математика - файл n2.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скачать

n2.doc





Пример. Вычислим Раскрывая скобки последовательно, производя умножение многочлена на многочлен и приводя подобные члены, получим Всего в выражении десять членов. Этот же результат легко получается по полиномиальной формуле (1.6.2) при Система условий суммирования здесь имеет вид Различных числовых коэффициентов тоже три: Для более удобного написания конечного результата лучше составить таблицу всех возможных комбинаций индексов , и .








3

0

0

0

3

0

0

0

3

2

1

0

2

0

1

1

2

0

0

2

1

1

0

2

0

1

2

1

1

1


Тогда , что то же самое, что было получено раньше.
§ 1.7. Метод рекуррентных соотношений.
В комбинаторном анализе существует целый ряд подходов для изучения комбинаторных объектов и чисел.

  1. Теоретико - множественный подход. Он связан с вычислениями мощностей конечных множеств. Для решения таких вопросов необходима дополнительная информация, то есть надо заранее знать мощности некоторых подмножеств. К этому пункту относится, например, теорема и формула включения и исключения.

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

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

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

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

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

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

(1.7.1)

Покажем , что справедливо равенство Здесь - общее число - выборок из множества с элементами. - число - выборок, то есть чис-

первый элемент ло выборок, не содержащих один (например,

первый) элемент из множества с эле-

ментами. В этом случае - множество

- множество - мно- становится - множеством, так как пер-

жество вый элемент не выбирается, он фиксирован.

- число - выборок из - множества, со-

держащих первый элемент. Этот элемент в

первый элемент множестве содержится всякий раз, то есть

фактически выбираются элементов,

- множество - мно- кроме того первый элемент опять фиксиро-

жество ван и в множестве , как в предыдущем

случае, и он не выбирается из - множества,

которое тогда становится - множеством.

По правилу суммы Применим эту формулу последовательно раз. Получим ,

,

,

.............................



Но , тогда окончательно

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

Для вывода общей формулы нам потребуется еще одно вспомогательное соотношение Иллюстрацией дальнейших рассуждений служит тот же ри-

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

По правилу суммы Применим теперь эту формулу для получения доказываемого исходного соотношения Именно . Отсюда получим Аналогично . Отсюда можно получить формулу для . Выполним аналогичные подстановки как в предыдущем случае, получим В данном случае лучше не суммировать отрезок числового ряда, а воспользоваться только что полученной формулой для предыдущего индекса Тогда так как . Но Таким образом, получена очередная формула . Формулы для последующих индексов получаются совершенно аналогично. Видно, что доказательства с помощью рекуррентных соотношений весьма громоздкое и утомительное занятие.
Глава 2. Метод производящих функций.
Этот метод не является элементарным, так как при его использовании приходится иметь дело с некоторыми понятиями теории функциональных рядов. Метод производящих функций является одним из самых развитых теоретических методов комбинаторного анализа и одним из самых сильных в приложениях. Главные идеи этого метода были высказаны в конце восемнадцатого века в работах Лапласа по теории вероятностей. Для случаев с конечным числом исходов аппарат теории вероятностей чисто комбинаторный.
§ 2.1. Производящие функции, основные понятия и определения.
Рассмотрим произведение конечного числа линейных биномов Коэффициенты в правой части равенства имеют вид

Это легко проверить, например, для случая малых . Пусть

Тогда Для проверяется ано-



Пьер Симон Лаплас (1749-1827 г.г.) - французский математик, механик и астроном.

логично. В частном случае, когда в качестве коэффициентов получим числа - сочетаний, то есть

(2.1.1)

В выражении (2.1.1) функция и числа связаны взаимно однозначно. Функцию называют производящей функцией последовательности .

Производящей функцией последовательности называется сумма степенного ряда

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

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

Пример 2. Пусть Тогда

. Это бесконечно убывающая геометрическая прогрессия со знаменателем Если , то ряд сходится и его сумма Итак,

(2.1.3)

Пример 3. Рассмотрим формулу бинома Ньютона при действительном показателе . Пусть , тогда то есть

(2.1.4)
Если то . Но
и так далее. Тогда , то есть

(2.1.5)

Пример 4. Пусть Тогда Действительно, Итак, для такой числовой последовательности получена производящая функция.

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

Введем несколько операций в классе производящих функций: - класс обычных производящих функций .

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

(2.1.6)

Произведением (или сверткой) последовательностей называется последовательность , у которой

, (2.1.7)

а произведением (сверткой) производящих функций и - производящую функцию (2.1.8)

Формулы (2.1.7) нуждаются в пояснении. Эти коэффициенты получаются при перемножении рядов следующим образом

(2.1.9)

Нуль в классе производящих функций это ; ей соответствует нулевая последовательность .

Единица в классе производящих функций это ; ей соответствует единичная последовательность .

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

Обратный элемент относительно умножения в классе производящих функций есть ей соответствует последовательность причем

Так как , то, учитывая формулы (2.1.9), получим систему



Неизвестные здесь , количество неизвестных равно количеству уравнений.

Умножение производящей функции на действительное число определяется по формуле (2.1.10)
§ 2.2. Получение некоторых производящих функций.

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

повторений.
В этом случае для получения производящей функции нельзя воспользоваться произведением биномов вида , то есть формулой , поскольку всякий такой бином отражает лишь две возможности: элемент множества либо не появляется в - сочетании, либо появляется ровно один раз.

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

Если нужно найти лишь число соответствующих - сочетаний, то необходимо положить и

(2.2.2)

Коэффициенты будут здесь равны числу сочетаний из элементов по с повторениями.

Пример. Рассмотрим сочетания из трех предметов 1, 2, 3; причем 1 и 2 могут встречаться не более двух раз, а 3 - не более одного раза.

Составим производящую функцию по формуле (2.2.1). Она будет равна



Если положить , то получим Здесь коэффициент равен числу сочетаний из трех по одному элементу не более чем с двумя повторениями, - из трех элементов по два не более чем с двумя повторениями, - из трех по три элемента с ограничениями, что первый и второй элемент могут встречаться не более двух раз, а третий не более одного раза. Если же не приравнивать , то, например, коэффициент при равный показывает «качественный» состав - сочетаний с указанными повторениями: 112, 113, 122, 123, 223. Аналогично коэффициент при - число - сочетаний из трех элементов по пять, но с повторениями, тогда такое возможно. Именно,
б). Производящая функция для - сочетаний с неограниченным

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

(2.2.3)

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

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