Дискретная математика 3 (стр. 2 из 10)

# 123 и 132 – одинаковые сочетания.

Общее число сочетаний обозначают С

. Определим это число

# Число сочетаний из 5 элементов по 3.

1, 2, 3, 4, 5.

123 134 234 345

124 135 235

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. Сдвиг начала вправо.

Пусть последовательность {b_k} определяется через {a_k} следующим образом: b_k=0 для k=0, 1, …, i-1 и b_k=a_k-i для k=i, i+1, …. Тогда, В(х)=хⁱA(x). Действительно,