3. Основные комбинаторные соединения (перестановки, сочетания и размещения с повторением и без повторений элементов).
Формулы пересчета для основных видов комбинаторных соединений
Соединения |
Без повторений элементов |
С повторениями элементов |
Сочетания |
|
|
Размещения |
|
|
Перестановки |
|
|
Соединения без повторений
Соединения – простые комбинаторные объекты, к которым относятся перестановки, сочетания и размещения.
1 Перестановка из n элементов – упорядоченная последовательность элементов n-элементного множества (кортеж).
Различные перестановки отличаются только порядком элементов в них.
Число
перестановок
из
n
различных
элементов равно:
2 Размещения – упорядоченная последовательность из m элементов множества, содержащего всего n элементов.
Различные размещения отличаются составом элементов и (или) порядком их следования.
Число
размещений
из
n
различных
элементов по
m
равно
3 Сочетания из n по m – последовательность из m элементов, взятых из n-элементного множества, без учета порядка следования элементов.
Сочетание – произвольное (неупорядоченное) m-подмножество из n элементов.
Различные сочетания отличаются составом элементов, но не их порядком.
Число
сочетаний из
n
различных
элементов по
m
равно:
,
m
≤ n.
Свойства сочетаний
;
2)
;
; 
;
при m
0 и m
n
.
3)
Симметричность числа сочетаний:
.
4)
Правило Паскаля. Для числа сочетаний
из n
по m
справедливо следующее рекуррентное
соотношение:
.
5) Бином Ньютона.
.
При
a
= x
= 1, 
, 
,где
,
k
= 0,1… n
- биномиальные коэффициенты.
Соединения с повторениями
Пусть дано множество А, состоящее из n элементов, в котором n1 элементов принадлежит первому типу; n2 элементов принадлежит второму типу элементов, nk - k-тому типу. Элементы одного и того же типа неразличимы между собой.
Спецификацией множества А называется набор (n1, n2, … ,nk).
Следствие:
Если
множество А, | А | = n,
состоит из объектов 2 типов: m-одного
типа, (n
– m)
–другого:
Число перестановок с повторениями n - элементного множества с
заданной спецификацией равно
,
где
.
В общем случае:
.
1 Размещения с повторениями
(m перестановки с неограниченными повторениями)
Пусть А = {a1, a2,…, an} , где a1, a2,…, an – “представители” 1-го, 2-го, … n-го типа элементов. Объектов каждого типа имеется в неограниченном количестве, элементы одного типа неразличимы между собой. Рассмотрим следующую схему выбора упорядоченной последовательности из m элементов: выбираем элемент на 1-е место, имеется n вариантов выбора. После этого элемент возвращается обратно и может быть выбран еще, т.е. на 2-е место имеется n претендентов и т.д. На m-е место также имеется n претендентов.
Число
различных размещений с повторениями
из n по m
равно Здесь
может быть m > n,
m < n, m
= n.
.
Сочетания с повторениями
Пусть А = {a1, a2,…, an}, где a1, a2,…, an - “представители” 1-го, 2-го, …, n-го типа элементов. Объектов каждого типа имеется в неограниченном количестве, элементы одного типа неразличимы между собой.
Сочетания с повторениями отличаются составом элементов, входящих в выбираемое множество. Порядок элементов не имеет значения. Имеет значение, сколько элементов каждого типа вошло в сочетание.
Число
различных сочетаний с повторениями
из n по m
равно:
