Реферат: Дискретная математика 3

125 145 245

В общем случае составим все сочетания из n по k. Затем переставим в каждом сочетании элементы всеми возможными способами. Получаем расстановки, отличающееся либо составом, либо порядком, то есть это все размещения без повторений из n элементов по k местам. Их число А. Учитывая, что каждое сочетание дает k! размещений, получаем: С∙k!=A. Следовательно, С=. Из формулы непосредственно следует, что С=С.

Пример. Сколькими способами из 7 человек можно сформировать комиссию, состоящую из трех человек?

С==35.

§6. Сочетания с повторениями.

Имеются предметы n различных видов число элементов каждого вида неограниченно. Сколько существует расстановок длины k, если не принимать во внимание порядок элементов? Такие расстановки называются сочетаниями с повторениями и обозначаются .

Пусть а, b, с, …, d– исходные различные типы элементов, количество которых n. Рассмотрим произвольное сочетание с повторениями cbbcaccda…ccbbb из данных типов элементов. Так как порядок элементов не учитывается, то расстановку можно записать так: aa…a|bb…b|cc…c|…|dd…d где элементы каждого из типов завершается вертикальной чертой, за исключением последней серии элементов. Длина такой расстановки с учетом вертикальных линий составляет k+(n-1)=n+k-1, где k – количество элементов в расстановке, (n-1) – число вертикальных линий. Очевидно, что любую такую расстановку можно задать выбором из n+k-1 мест n-1 место для положений вертикальных линий. Это можно сделать С способами. Промежуточные места между линиями заполняются соответствующими типами элементов. Таким образом, =С=С.

Пример. Трое ребят собрали в саду 7 яблок. Сколькими способами они могут их разделить между собой?

Решение. Поставим в соответствие каждому делению яблок между ребятами сочетание с повторениями следующим способом. Типами элементов в нашем случае будут ребята. Таким образом, имеем три типа элементов a, b, c (n=3) из которых предстоит составить все различные расстановки k=7. Наличие в расстановке какого либо из элементов a, b, с отвечает принадлежности данного яблока соответствующему мальчику. Порядок элементов в такой расстановке не играет роли. При делении яблок между ребятами не важно, какое из них попадет тому или иному мальчику. Тогда число способов разделить яблоки между ребятами равно

=С=С===36

§7. Перестановки с повторениями. Мультимножества.

Имеются предметы k различных видов. Сколько существует перестановок из n₁ элементов первого типа, n₂ элементов второго типа и т.д., n_k элементов k-го типа?

Рассмотрим например, мультимножество (множество, содержащее повторяющееся элементы): М={a,a,a,b,b,c,d,d,d,d}={3∙a, 2∙b, 1∙c, 4∙d}. Таким образом искомые перестановки мультимножества М. Если рассмотреть М как множество с различными элементами, обозначив их а₁ , а₂ , а₃ , b₁ , b₂ , c₁ , d₁ , d₂ , d₃ , d₄ , то получили бы 10! перестановок. Но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка множества М встретилась бы ровно 3!∙2!∙1!∙4! раз, так как в любой перестановке М индексы при буквах а можно расставить 3! способами, при буквах b – 2! способами, при с – одним способом, при d – 4! способами. Поэтому число перестановок множества М равно .

В общем случае Р(n₁ , n₂ , …, n_k )=, где n=n₁ +n₂ +…+n_k – общее число элементов.

Справедлива формула: Р(n₁ , …, n_k )=C.

Пример. Сколько существует различных перестановок из букв слова «математика»? Р(3а, 2т, 2м, 1е, 1и, 1к)==151200.

§8. Полиномиальная формула.

Формула (х₁ +х₂ +…+х_k )ⁿ = называется полиномиальной, где суммирование выполняется по всем решениям уравнения n₁ +n₂ +…+n_k =n в целых неотратимых числах, n_i ≥0, i=1,2,…k.

При k=2 получаем частный случай полиномиальной формулы – бином Ньютона (а+b)ⁿ =.

Методы подсчета и оценивания.

§1. Производящие функции.

Любая а₀ , а₁ , а₂ , … - произвольная последовательность. Сопоставим последовательности функцию действительного или компактного переменного

А(х)=(1)

Функция А(х) называется производящей функцией последовательности а₀ , а₁ , …. Как правило, поиск функции А(х) по формуле (1) прямыми методами является сложной задачей. Однако, последовательность {a_k } может быть восстановлена по А(х). Выражение (1) является разложением А(х) в ряд Маклорена. Приведем некоторые наиболее распространенные производящие функции и соответствующие им последовательности.

Производящие функции, А(х)	Последовательности, {ak }
	ak =1, k≥0
	ak =k+1, k≥0
	a0 =0, ak =, k≥1
	a0 =0, ak =, k≥1
	ak =, k≥0
	ak =, k≥0, r – любое
	ak =, k≥1, r – любое
	ak =, k≥0, r – любое

Простейшие производящие функции будем использовать для получения производящих функций более сложных последовательностей. С этой целью рассмотрим наиболее важные из операций над производящими функциями, то есть способы получения новых производящих функций и соответствующих им последовательностей. Обозначим через {a_k }, {b_k }, {c_k } последовательности, а соответствующие им производящие функции как А(х), В(х), С(х).

§2. Линейные операции.

Если α и β – константы, то последовательность c_k =αa_k +βb_k имеет производящую функцию С(х)=αА(х)+βВ(х).

# a_k =1 A(x)=

b_k =B(x)=e^x

c_k =100+C(x)=100A(x)+5B(x)=+5e^x .

§3. Сдвиг начала вправо.