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

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

1) Пусть все элементы исходной группы участвуют в создании комбинаций, , где m – количество элементов в комбинации.

Пример Найти количество последовательностей номеров из цифр .

Получим следующие комбинации: . (6 шт.)

Комбинации отличаются одна от другой только порядком следования элементов. Такие комбинации называются ПЕРЕСТАНОВКИ, обозначаются Р_n и количество всех перестановок из n элементов равно ; .

В примере n = 3; .

2) Пусть не все элементы исходной группы участвуют в создании комбинаций, .

Пример1 Составить все возможные отношения из трех чисел а, в, с по два числа (без повтора элементов).

Получим следующие комбинации: . Их 6 шт. и они отличаются одна от другой или элементами, или порядком их следования, или тем и другим. Такие комбинации называются РАЗМЕЩЕНИЯ, обозначаются и количество всех размещений из n элементов по m равно

В примере .

Пример2 Составить все возможные произведения из трех чисел по два числа (без повтора элементов).

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

Такие комбинации называются СОЧЕТАНИЯ, обозначаются и количество всех сочетаний из n элементов по m равно .

Важное свойство сочетаний , отсюда

В примере .

3) Правило произведения

Пусть имеем множество элементов и множество .

Один элемент можно выбрать k способами элемент у_i Î У можно выбрать т способами. Тогда пару элементов одновременно можно выбрать способами: каждый х_i сочетается с каждым y_j.

Пример Из города А в город В можно добраться самолетом и поездом, из В в С – автобусом, поездом и пароходом. Сколько различных возможностей (маршрутов) добраться из города А в город С?

.