СОЧЕТАНИЯ БЕЗ ПОВТОРЕНИЙ

ТЕМА 11: ОСНОВНЫЕ ПОНЯТИЯ И ПРАВИЛА КОМБИНАТОРИКИ

Комбинаторика – раздел дискретной математики, посвящённый решению задач выбора и расположения элементов некоторого конечного множества в соотношении с заданными свойствами.

ОСНОВНЫЕ ПРАВИЛА КОМБИНАТОРИКИ

ПРАВИЛО ПРОИЗВЕДЕНИЯ:

Пусть необходимо выполнить к-действий последовательно. Если первое действие возможно выполнить n1 способами, второе n2 способами, а к-ое nk способами, то все действия можно выполнить n1*n2*…*nk способами.

ПРАВИЛО СУММЫ:

Если элемент Х может быть выбран M способами, а элемент У другими N способами, то выбор либо Х, либо У может быть выбран M+N способами.

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

РАЗМЕЩЕНИЕ БЕЗ ПОВТОРЕНИЯ

Пусть А – конечное множество, состоящее из N элементов (|A| = N).

Кортежи длины K (K=1,n), состоящее из различных элементов N-элементного множества (кортежи отличаются друг от друга как самими элементами, так и их порядком) называют размещением из N элементов множества А по К, А_N^K.

Схема выбора состоит в выборе К элементов из N элементного множества без возвращений. Тогда необходимо совершить К действий, причем первое действие можно совершить N способами, второе – (N-1) способами,

К-ое – (N-(K-1)) и т.д. Согласно комбинаторному правилу умножения, получим формулу:

А_N^K=N*(N-1)*…*(N-K+1)

Если умножить и разделить полученное выражение на (N-K)!, получим:

А_N^K=N!/(N-K)!

ПРИМЕР:

Дано множество А={1,3,5}

А₃²= 3!/(3-2)!=6

ОТВЕТ : 6

МЕТОД ПЕРЕСТАНОВКИ

Пусть А – конечное множество N элементов. Будем строить из этого множества размещения в виде кортежей N. Эти размещения будут отличаться друг от друга только порядком элементов, поскольку в каждом из них встречаются по одному разу все элементы множества А. Такие размещения называются перестановками P_n . Поскольку P_n = A_n, то число перестановок высчитывается по формуле:

P_N=А_N=N!/(N-N)!=N!

Перестановки элементов записываются в матричной форме.

ПРИМЕР:

|1 3 5|

f1 = | |

|1 3 5|

f2 = | |

|3 5 1|

|1 3 5|

f3 = | |

|5 1 3|

|1 3 5|

f4 = | |

|5 3 1|

|1 3 5|

f5 = | |

|3 1 5|

|1 3 5|

f6 = | |

|1 5 3|

СОЧЕТАНИЯ БЕЗ ПОВТОРЕНИЙ

Пусть А- конечное множество из N- элементов. Будем строить наборы длины К. Не учитывая порядок элементов, т.е. размещение с одними и теми же элементами, расположенными в разном порядке, будем считать равными.

Такие размещения называются сочетаниями и обозначаются С_N^K.

ПРИМЕР:

Какие парные сочетания можно составить из A={1,3,5} и сколько их?

С_N^K= A_N^K/P_K=N!/((N-K)!*K!)

Выпишем парные сочетания:

{1,3},{3,5},{1,5}

С_N^K=3

ОТВЕТ: 3