Часть IV. ОСНОВЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКОЙ СТАТИСТИКИ

ГЛАВА 9. ОСНОВЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ

9.1. ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

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

Определение

Перестановкой из n элементов называется каждая последовательность этих элементов в каком-либо порядке.

Поскольку каждая перестановка содержит все n элементов, то различные перестановки отличаются друг от друга только порядком следования элементов. Число всех возможных перестановок из n элементов обозначают P_n, которое равно произведению всех натуральных чисел от 1 до n:

P_n = 1 ? 2 ? 3 ? ? ? n = n!

(читается «эн факториал»).

Например, все возможные перестановки букв а, b, с: а, b, с; а, с, b; b, а, с; b, с, а; с, а, b; с, b, а. Всего 6 перестановок, что соответствует:

P₃ = 1 ? 2 ? 3 = 6.

Пример 9.1. Сколько имеется вариантов расстановки 5 книг на одной полке?

Решение. Искомое число вариантов равно:

P₅ = 1 ? 2 ? 3 ? 4 ? 5 = 120. ᐊ

При нахождении факториалов следует помнить, что 0! = 1! = 1. Иногда задача заключается в упорядочении не всех n объектов, а лишь некоторой последовательности из k объектов. Такие упорядоченные последовательности называются размещениями из n элементов по k элементов.

Определение

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

Число размещений из n элементов по k обозначается A_n^k (читается «А из n по k») и вычисляется по формуле:

Например, из трех букв а, b, с можно составить три размещения по одной букве, шесть размещений по две буквы: а, b; а, с; b, a; b, с; с, а; с, b; и шесть размещений по три буквы: a, b, c; а, с, b; b, а, с; b, с, а; с, а, b; с, b, а. Проверим по формуле: