Элементы комбинаторики

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

Множество наз. Упорядоченным, если в нем указан порядок следования элементов. Например

Основные правила комбинаторики

1.Правило суммы

Пусть из множества А элемент а1 можно выбрать n1 способами, элемент а1-n1 способами, а2-n2 способами,…, аk-nk спосбами. Тогда выбор одного из этих элементов или а1, или а2,…, или аk можно произвести n1+n2+…+nk способами.

2.Правило произведения

Пусть из множества А элемент а1 можно выбрать n1 способами, элемент а1-n1 способами, а2-n2 способами,…, аk-nk спосбами. Тогда одновременный выбор элементов а1,а2,…,аk можно выбрать n1*n2*…*nk способами.

Пример

Из 3-ех классов спорт. школы нужно составить команду для соревнований, взяв по одному ученику из класса. Сколько команд можно составить, если в одном классе 18 учеников, в другом-20, в третьем-22.

Решение:n1=18, n2-20, n3=22

n1*n2*n3=18*20*22=7820 способов.

Основные соединения комбинаторики.

1)Размещения

Пусть множество А состоит из n элементов. Будем выбирать из оттого множества упорядоченные множества, состоящие из k элементов. Такие подмножества будут называться размещениями из n элементов по k . Размещения отличаются друг от друга как элементами, так и порядком.

Например , из множества  составим размещения по 2 элемента. , , , , ,

Число размещений из n элементов по k обозначают  и вычисляют по формуле:  ; (0!=1)

2)Перестановки из n элементов k

Перестановками из n элементов по k называют размещения, у которых n=k. Перестановки отличаются только порядком элементов. ; ; ; ; ;

Число перестановок из n элементов по k (n=k):

3)Сочетания из n элементов по k

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

Число сочетаний из n элементов по k:

Примеры:

1)Студентам нужно сдать сдать 4-ре экзамена за 8 дней. Сколькими способами можно составить расписание?

(2,3,7,8) Из множества, содержащего 8 элементов выбираем подмножества по 4 элемента, порядок которых нам не безразличен, следовательно число способов:

2)На 4-ех карточках написаны цифры 0,1,2,3. Сколько различных четырехзначных чисел чисел можно составить из этих карточек?

4!-3!=24-6=18

3)В хоккейном турнире участвует 6 команд. Каждая команда должна сыграть с каждой одну игру. Сколько игр будет сыграно в турнире?

Т.к в выбираемых множествах по 2 элемента из 6, порядок безразличен, то кол-во игр=числу сочетаний из 6 по 2:

4)6 друзей собрались на встречу. Один из них произнес тост: собираться столько лет пока каждый не посидит на новом месте.