Лабораторная работа №5. Тема: «Основные понятия комбинаторики»
1 Теоретические сведения
Правила суммы и произведения
Важную роль при решении многих комбинаторных задач играют 2 правила: правило суммы и произведения.
Сформулируем эти правила с точки зрения теории множеств и комбинаторики.
Правила суммы
- Теоретико – множественная формулировка
Пусть A – множество из m элементов; B – множество из n элемнтов. AÇB=Æ. Тогда, объединение множеств: AÈB содержит m+n элементов.
В общем случае: Пусть |M1|=m1, |M2|=m2, …, |Mk| = mk и Mi Ç Mj=Æ "i,j=1.. k, i¹j. Тогда, |M| = |M1È M2È…ÈMk| = m1+ m2+…+ mk.
- Комбинаторная формулировка
Если объект a может быть выбран m способами, а объект b – n другими способами, то выбор "a или b" может быть осуществлен m+n способами.
Выбор a и b – взаимоисключающий, выбор a исключает выбор b; выбор a не совпадает с каким-либо способом выбора b.
В общем случае:
Если объект a1 может быть выбран m1 способами; … ak – mk способами. Выбор "a1 или a2…или ak " может быть осуществлен m1 +m2 +…+mk способами.
Например: Из Киева в Донецк в течении суток отправляется 3 поезда, 1 самолет и 2 автобуса. Сколько существует способов выехать из Киева в Донецк?
Решение: По правилу суммы имеем N= 3+1+2 = 6 способов.
Правило произведения
- Теоретико – множественная формулировка
Если A и B – конечные множества и |A|=m, |B|=n, то мощность множества A´B равна m´n.
В общем случае; если |M1|=m1, |M2|=m2, …, |Mk|=mk, то |M1´M2´…´Mk|= =m1´m2´…´mk.
- Комбинаторная формулировка
Если объект a может быть выбран m способами, и после этого объект b может быть выбран n способами, то выбор пары (a,b) может осуществляться m´n способами (выбор a и b независимы).
В общем случае:
Пусть объект a1 может быть выбран m1 способом; объект a2 – m2 способами; … ak – mk способами, причем выбор a1 не влияет на число способов выбора a2 …ak, выбор a2 на число способов выбора a3 …ak, … Тогда, выбор упорядоченного множества объектов (a1, a2 …ak) – в указанном порядке можно осуществить m1´ m2´… ´mk способами.
Например: Сколько различных танцующих пар можно составить из 3-х девушек и 2-х юношей?
Решение: По правилу произведения имеем N= 3´2=6 пар.
Сложный выбор объектов
Часто в комбинаторных задачах выбор объектов происходит в несколько ступеней, на некоторых работает правило суммы, на других – правило произведения. При сложном выборе объектов важно обеспечить полный перебор всех возможных случаев.
Например: Имеется три различных флага. На флагштоке поднимается сигнал, состоящий не менее, чем из 2-х флагов. Сколько различных сигналов можно поднять на флагштоке, если порядок сигналов учитывается?
Решение: Сигнал может состоять либо из 2-х сигналов, либо из 3-х. Одновременное выполнение 2-х действий невозможно.
N=N2+N3 (правило суммы)
N2=3´2=6 (правило произведения)
N3=3´2´1=6 (правило произведения)
N=12
Соединения без повторений
Соединения – простые комбинаторные объекты, к которым относятся перестановки, сочетания и размещения.
Перестановки
Перестановка из n элементов – упорядоченная последовательность элементов n- элементного множества (кортеж).
Различные перестановки – отличаются порядком элементов в них.
Например:
Пусть A={1,2,3}
Перестановки: 123, 132, 213, 231, 312, 321.
Число перестановок из n различных объектов равно: Pn=n!
Определим n!=1*2*3*…*n, 0!=1, n!=(n-1)!*n
Например:
1. Число способов стать в очередь за стипендией из 17 человек?
P17=17!
2. Сколькими способами можно расставить на полке 5 книг?
P5=5!
3. Сколько различных слов можно образовать, переставляя буквы в слове "ковш"?
P4=4!
Размещения
Размещения – упорядоченная последовательность из m элементов множества, содержащего всего n элементов.
Различные размещения – отличаются совокупностью элементов и (или) порядком их следования.
Например:
Пусть A={1,2,3}
Размещения из 3 по 2: 12, 21, 13, 31, 23, 32.
Число размещений из n по m равно: 
Например:
1. Сколькими способами можно расставить на полке 5 книг из 7?
2. Сколько различных 4х символьных идентификаторов можно получить в алфавите {A,B,C,D,E}.
Замечание:
Формула 
верна для всех m£n.
При m=n 
= 
=Pn.
Сочетания
Сочетания из k по m – набор из m элементов, без учета порядка элементов в наборе. Сочетание – произвольное неупорядоченное m-подмножество из n элементов. Различные сочетания – отличаются набором элементов, но не их порядком.
Например:
A={1,2,3}
Сочетания из 3 по 2: 12, 31, 32.
Число сочетаний из n различных объектов по m равно:
, m<n.
Anm=Cnm*m! Þ Cnm= 
= 
Свойства сочетаний
 |  |  | |||
при k£0 и k ³n
2 Симметричность числа сочетаний:
3 Правило Паскаля:
Для числа сочетаний из n по m справедливо следующее рекуррентное соотношение:
 |
4 Треугольник Паскаля
 |
Числа, n=0,1 … выпишем в виде треугольника:
 |
n=0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
 |  |  | |||||||
 | |||||||||
|
Коэффициенты − биноминальные коэффициенты в выражении, которое известно, как бином Ньютона.
При a=x=1
 |  | ||||
 | |||||
, если, - число k-элементных подмножеств
 |
Соединения с повторениями
До сих пор рассматривали соединения из множеств, состоящих из различных элементов. Часто на практике имеют место случаи, когда среди рассматриваемых элементов есть одинаковые.