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

Комбинаторика – наука, изучающая количества комбинаций, подчиненных определенным условиям.

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

Пример 1. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в число один раз?

Решение. .

Ответ: 6 чисел (123, 213, 231, 132, 312, 321).

Размещениями называются комбинации, составленные из элементов по элементов в каждой, которые отличаются либо составом, либо их порядком.

Число всех размещений без повторений равно

.

Пример 2. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3, 4, если каждая цифра входит в изображение числа один раз?

Решение. .

Ответ: 12 чисел (12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43).

Сочетаниями называются комбинации, составленные из элементов по элементов в каждой, которые отличаются только составом.

Число всех сочетаний без повторений равно

.

Пример 3. Сколькими способами можно выбрать две цифры из четырех?

Решение. (первая и вторая, первая и третья, первая и четвертая, вторая и третья, вторая и четвертая, третья и четвертая).

Ответ: шестью способами.

Правило суммы. Если множество можно выбрать n способами, а множество – способами, то множество «либо , либо » можно выбрать способами.

Пример 4. Если в комнате находятся два кресла и три стула, то вошедший может присесть 2 + 3 = 5 способами: либо на первое кресло, либо на второе, либо на первый стул, либо на второй, либо на третий.

Правило произведения. Если множество можно выбрать n способами, а множество – способами, то пара может быть выбрана (n×m) способами (одновременное выполнение).

Пример 5. Из Киева до Чернигова можно добраться пароходом, поездом, автобусом или самолетом. Из Чернигова до Ново-Северского пароходом или автобусом. Таким образом, путешествие из Киева до Ново-Северского можно осуществить 4 × 2 = 8 способами:

пароход

Киев поезд пароход

ЧерниговНово-Северский