Открытая Математика. Алгебра. Размещения

Размещения

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

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

Символ $A_{n}^{k}$ читается «а из эн по ка».

Размещения

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

Перестановки

Другими словами, $P_{n} = A_{n}^{n} .$ Выведем формулу для числа $A_{n}^{k} .$ Первый элемент выборки можно выбрать n различными способами, второй – n − 1 способом, ..., k-й − n − (k − 1) способом. Значит, k элементов можно выбрать $A_{n}^{k} = n ċ (n - 1) ċ (n - 2) ċ ... ċ (n - k + 1)$ способами. В частности, P_n = n ċ (n – 1) ċ ... ċ 2 ċ 1.

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

Количество размещений из n элементов по k: $A_{n}^{k} = \frac{n!}{(n - k)!} .$

В частности, количество перестановок из n элементов: P_n = n!.

Вычислить $A_{4}^{2} .$

$A_{4}^{2} = \frac{4!}{(4 - 2)!} = \frac{4!}{2!} = 3 ċ 4 = 12 .$

Ответ. 12.

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

При больших n выражение n! можно приближенно вычислить по формуле: $n! \approx {(\frac{n}{e})}^{n} ċ \sqrt{2 π n} .$

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

Вернемся к формуле $P_{n} = A_{n}^{n} .$ Из неё следует, что $P_{n} = \frac{n!}{(n - n)!} = \frac{n!}{0!} .$ В подобных ситуациях полагают, что 0! = 1, и это логично: единственный способ переставить 0 объектов – это ничего не делать.

Сколько семизначных чисел, кратных 5, можно составить из цифр при условии, что цифры в записи числа не повторяются?

Последняя цифра искомого числа должна быть 0 или 5. В первом случае остальные шесть цифр можно выбирать из множества {1, 2, 3, ..., 9}, и число вариантов равно $A_{9}^{6} = \frac{9!}{3!} = 60480 .$ Пусть теперь число оканчивается цифрой 5. Тогда в качестве первой цифры можно взять любую из цифр 1, 2, 3, 4, 6, 7, 8, 9. Цифры со второй по шестую можно выбрать $A_{8}^{5} = \frac{8!}{3!} = 6720$ способами. Значит, всего таких семизначных цифр существует $A_{9}^{6} + 8 ċ A_{8}^{5} = 114240 .$ Ответ. 114240.

В предыдущем примере цифры в числе не должны были повторяться. Не менее часто, однако, встречаются задачи, в которых элементы в выборке могут повторяться. Подобные выборки называются размещениями с повторениями и обозначаются ${\tilde{A}}_{n}^{k} .$

Найдем число ${\tilde{A}}_{n}^{k} .$ На первое место можно выбрать элемент n способами, на второе – также n способами, и так далее. Если количество мест равно k, то по правилу количество различных выборок равно

Количество размещений с повторениями обозначается символом ${\tilde{A}}_{n}^{k}$ и вычисляется по формуле ${\tilde{A}}_{n}^{k} = n^{k} .$

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

По формуле

{\tilde{A}}_{n}^{k} = n^{k},

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

{\tilde{A}}_{n}^{k} = 26^{5} =11881376 .

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

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

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

Количество перестановок из n элементов, среди которых имеется n₁ одинаковых элементов первого сорта, n₂ одинаковых элементов второго сорта, n_k одинаковых элементов k-го сорта, называется количеством перестановок с повторениями, обозначается символом ${\tilde{P}}_{n_{1}, n_{2}, ..., n_{k}}$ и вычисляется по формуле ${\tilde{P}}_{n_{1}, n_{2}, ..., n_{k}} = \frac{(n_{1} + n_{2} + ... + n_{k})!}{n_{1}! n_{2}! ... n_{k}!} .$

Смотрите также: Математика, Английский язык, Химия, Биология, Физика, География, Астрономия.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".

Учебник. Размещения

ГЛАВНАЯ

НОВОСТИ

УЧЕБНИК

ДОСТУП К БЕСПЛАТНЫМ УРОКАМ