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

Задача. Определить количество всех упорядоченных наборов длиныr, которые можно составить из элементов множестваX (), если выбор каждого элемента, производится из всего множестваX.

Упорядоченный набор – это элемент декартова произведения , состоящего изrодинаковых множителейX. По правилу произведения количество элементов множестваравно . Мы вывели формулу.

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

Здесь , и количество телефонных номеров равно

2.1.5. Размещения без повторений

Задача. Сколько упорядоченных наборовможно составить изnэлементов множестваX, если все элементы набора различны?

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

Эта формула записывается иначе с использованием обозначения . Так как

то

.

Пример. Сколько может быть различных списков победителей олимпиады (первое, второе, третье место), если участвовало 20 человек?

Здесь , искомым является число

2.1.6. Перестановки без повторений

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

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

.

2.1.7. Перестановки с повторениями

Пусть множество Xсостоит изkразличных элементов:.Перестановкой с повторениями составабудем называть упорядоченный набор длины, в котором элементвстречается раз . Количество таких перестановок обозначается.

Пример. Из буквзапишем перестановку с повторением состава. Ее длина, причем букваaвходит 2 раза,b– 2 раза,c– один раз. Такой перестановкой будет, например,или.

Выведем формулу количества перестановок с повторениями. Занумеруем все одинаковые элементы, входящие в перестановку, различными индексами, т.е. вместо перестановки получим. Теперь все элементы перестановки различны, а количество таких перестановок равно. Первый элемент встречается в выборкераз. Уберем индексы у первого элемента (в нашем примере получим перестановку), при этом число различных перестановок уменьшится в раз, т.к. при изменении порядка одинаковых элементов наша выборка не изменится. Уберем индексы у второго элемента – число перестановок уменьшится в раз. И так далее, до элемента с номеромk– число перестановок уменьшится в раз. Получим формулу

Пример. Сколько различных “слов” можно получить, переставляя буквы слова “передача” ?

В этом слове буквы “е” и “а” встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава длины. Количество таких перестановок равно

.

2.1.8. Сочетания

Задача. Сколько различных множеств изrэлементов можно составить из множества, содержащегоnэлементов?

Будем составлять вначале упорядоченные наборы по rэлементов в каждом. Количество таких наборов (это размещения изnэлементов поr) равно. Теперь учитываем, что порядок записи элементов нам безразличен. При этом изразличных размещений, отличающихся только порядком элементов, получим одно сочетание. Например, два различных размещения ииз двух элементов соответствуют одному сочетанию. Таким образом, число сочетанийвраз меньше числа размещений:

Пример. Количество способов, которыми мы можем выбрать из восьми дворников троих равно