Размещения с повторениями

Если выбор элементов подмножества из множества, А происходит с возвращением (повторением), т. е. каждый элемент подмножества может быть выбран несколько раз с учетом порядка (выбор с повторениями и учетом порядка), то число размещений из п по т находится по формуле Такой способ выбора в комбинаторике носит название выборки с повторениями.

Пример 1.1. Пусть даны шесть цифр: 1, 2, 3, 4, 5, 6. Определить сколько трехзначных чисел можно составить из этих шести цифр.

Решение. Выборка из шести цифр является упорядоченным множеством из 6 элементов по 3 элемента (выбор без повторения и с учетом порядка). Допустим, что цифры не повторяются. Общее количество трехзначных из этих цифр получим, воспользовавшись формулой числа размещений из 6 по 3:

или Теперь рассмотрим случай, когда цифры повторяются. Всего имеется 6 элементов — 6 цифр; в образовании различных размещений участвуют все 6 цифр, причем различные размещения содержат повторяющиеся цифры. Следовательно, эти соединения являются размещениями с повторениями. По формуле (1.3) получим:

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

Решение. Состав комиссии является упорядоченным множеством из 20 элементов по 3 элемента (выбор без повторения и с учетом порядка). Следовательно, число возможных вариантов комиссии равно числу размещений из 20 элементов по 3 элемента в каждом:

или.

Пример 1.3. Группа студентов из 10 человек обменялась фотокарточками. Сколько всего было роздано фотокарточек?

Решение. Обмен фотокарточками одним студентом с другим есть размещение из 10 элементов по 2 элемента. Поэтому искомое число фотокарточек или.

Перестановки. Размещения из п элементов по и элементов называются перестановками из п элементов. Из определения следует, что перестановки являются частным случаем размещений. Различные перестановки из п элементов отличаются друг от друга только порядком следования элементов (выбор без повторения и с учетом порядка).

Так, например, перестановки множества А = {а, Ь, с} из 3 элементов имеют вид

Следовательно, множество А из 3 элементов можно упорядочить 6 способами.

Число перестановок из п элементов данного множества обозначают Р" и вычисляют по формуле.

Пример 1.4. Сколькими способами можно разместить в четырех гнездах штатива холодильника четыре пробирки с группами крови 0(1), л (и), Я (Ш) и /<�й (1У)?

Решение. Число всех возможных размещений в данном случае равно числу перестановок из 4 элементов (выбор без повторения и с учетом порядка), т. е.

Пример 1.5. Сколько различных списков (отличающихся порядком фамилий) можно составить из 8 различных фамилий?

Решение. Р" = 8≠1−2-3−4 5−6-7−8 = 40 320.