Задачи для самостоятельного решения

1. В соревнованиях участвует 10 человек, трое из них займут
1-е, 2-е, и 3-е места. Сколько существует различных вариантов?

2. В хирургическом отделении работают 6 врачей. Сколькими способами из них можно образовать бригаду в составе хирурга и ассистента?

3. Сколькими способами можно составить различные двузначные числа из четырех цифр 1, 2, 3, 4, если цифры в записи числа не повторяются?

4. В гостинице 10 четырехместных номеров. Сколько существует вариантов размещения прибывших четырех гостей?

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

а) в одну коробку можно положить не более одного шара;

б) в одну коробку можно положить неограниченное число шаров?

6. Сколько пятибуквенных «слов» можно составить в алфавите из 10 букв, если:

а) буквы в «словах» не должны повторяться;

б) буквы в «словах» могут повторяться?

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

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

Одним из видов размещений являются перестановки.

Размещение из n элементов по n называется перестановкой из n элементов. Их число обозначают P n (от фр. permutation – перестановка).

Для нахождения числа Р _n заметим, что перестановка без повторений из n элементов – это то же самое, что размещение без повторений из n элементов по n, то есть

Заметим, что , а . Если множество содержит один элемент, то и вариант составления кортежей тоже единственный, но если во множестве нет элементов, то это тоже единственный вариант: «кортеж длины 0».

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

Пусть дан кортеж длины n, состоящий из элементов множества
А = {a₁, a₂, …, a _m } . Отсортируем в кортеже элементы: каждому числу k ставится в соответствие число n_k, показывающее сколько раз элемент a_k встретился в этом кортеже. Тогда Очевидно, что перестановка одинаковых элементов внутри некоторого k -го сорта не изменит кортежа, то есть среди n! всех перестановок будет n_k! тождественных. Уменьшим число перестановок из n (n!), убрав повторяющиеся кортежи обратным действием (разделив на n ₁!, n ₂!, …, n_m!). Тогда число перестановок с повторениями, имеющих такой состав, найдем по формуле: .