Глава 4. Комбинаторика

4.2.

4.2.2.

Пусть задано некоторое конечное множество из n различных элементов. Пусть из числа его элементов выбраны k различных штук (k ≤ n), тогда говорят, что произведена выборка объёма k. Если важен порядок, в котором произведена выборка элементов, то говорят об упорядоченной выборке, если порядок не важен, то о неупорядоченной.

	Упорядоченная выборка объёма k из множества, состоящего из n элементов, (k ≤ n) называется размещением из n элементов по k. Количество размещений обозначается

Символ читается «а из эн по ка».

Модель 4.3. Размещения

	Размещение из n элементов по n называется перестановкой из n элементов. Количество перестановок обозначается Pn.

Модель 4.2. Перестановки

Другими словами, Выведем формулу для числа Первый элемент выборки можно выбрать n различными способами, второй – n − 1 способом, ..., k-й − n − (k − 1) способом. Значит, k элементов можно выбрать

способами.

В частности, P_n = n · (n – 1) · ... · 2 · 1.

Введём следующее обозначение: n! = n · (n – 1) · ... · 2 · 1. Символ «!» называется знаком факториала или просто факториалом. По определению считается, что 0! = 1. С помощью факториала можно компактно записать выражение для и

Количество размещений из n элементов по k: В частности, количество перестановок из n элементов: Pn = n!.

Вычислять факториалы от больших чисел не очень удобно. Для больших n можно использовать оценочную формулу, предложенную шотландским математиком Джеймсом Стирлингом.

При больших n выражение n! можно приближенно вычислить по формуле:

Буквой e здесь, как обычно, обозначено основание натурального логарифма e = 2,71828… При n = 10 погрешность при вычислении факториала с помощью этой формулы составляет менее 1 %, а при n = 100 – меньше 1/10 процента.

Вернемся к формуле Из неё следует, что В подобных ситуациях полагают, что 0! = 1, и это логично: единственный способ переставить 0 объектов – это ничего не делать.

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

Найдем число На первое место можно выбрать элемент n способами, на второе – также n способами, и так далее. Если количество мест равно k, то по правилу количество различных выборок равно

	Количество размещений с повторениями обозначается символом и вычисляется по формуле

Пример 3

Сколько различных пятибуквенных «слов» можно составить из 26 букв латинского алфавита?

Показать решение

По формуле где n = 26, k = 5, получаем:

Пример 4

У Васи есть две одинаковых копейки, один десятицентовик, три одинаковых пенса и три одинаковых лиры. Сколькими способами Вася может разместить монеты в своем альбоме, если количество мест в альбоме в точности равно количеству монет?

1

Показать решение

При расстановке монет в альбоме важен порядок следования монет – значит, речь идет о количестве перестановок. Всего монет 9, и общее количество перестановок равно 9!. Однако если мы переставим местами две одинаковых копейки, то набор от этого не изменится. Значит, ответ нужно поделить на 2. Точно так же не изменится набор и в том случае, если переставить друг с другом пенсы или лиры. Количество перестановок 3 пенсов равно 3!, лир – также 3!. Десятицентовик у Васи всего один, и количество перестановок для него равно 1!, но для завершённости формулы учтём и его. Итак, количество способов, которыми можно расставить монеты в альбоме, равно

Можно сформулировать общее правило.

	Количество перестановок из n элементов, среди которых имеется n1 одинаковых элементов первого сорта, n2 одинаковых элементов второго сорта, nk одинаковых элементов k-го сорта, называется количеством перестановок с повторениями, обозначается символом и вычисляется по формуле