Составители:
Рубрика:
8
1.4. Перестановки с повторениями
Иногда требуется переставлять предметы, некоторые из которых
неотличимы друг от друга. Рассмотрим такой вариант перестано-
вок, который называется перестановками с повторениями.
Пусть имеется n
1
предметов 1-го типа, n
2
предмета 2-го, n
k
пред-
метов k-го типа и при этом n
1
+ n
2
+...+ n
k
= n. Количество разных
перестановок предметов
P(n
1
, n
2
, n
3
, ...n
k
) = (n!)/(n
1
! n
2
!...n
k
!) (5)
Для обоснования ( 5 ) сначала будем переставлять n предметов в
предположении, что они все различны. Число таких перестановок
равно n! Затем заметим, что в любой выбранной расстановке пере-
становка n
1
одинаковых предметов не меняет комбинации, анало-
гично перестановка n
2
одинаковых предметов также не меняет ком-
бинации и т. д. Поэтому получаем выражение (5).
П р и м е р. Найдем количество перестановок букв слова КОМ-
БИНАТОРИКА. В этом слове 2 буквы к, 2 буквы о, 1 буква м, 1
буква б, 2 буквы и, 1 буква н, 2 буквы а, 1 буква т и 1 буква р.
Таким образом, число перестановок букв этого слова равно: P(2,
2, 1, 1, 2, 1, 2, 1, 1) = 13!/(2! 2! 2! 2!)= 13!/16.
Упражнения
1. У школьника 2 авторучки, 4 карандаша и 1 резинка. Он раскла-
дывает эти предметы на парте в ряд. Сколько вариантов раскладки?
2. Рыбаки поймали 5 подлещиков, 4 красноперки и 2 уклейки, по-
солили и вывесили на солнце сушиться. Сколько вариантов развеши-
вания рыбы на нитке?
3. На узком участке трассы в линию движутся гонщики. Из них 5
на российских автомобилях, 6 – на американских и 3 – на итальянс-
ких. Сколько существует разных комбинаций машин на трассе, если
нас интересует только принадлежность автомобиля конкретной стра-
не?
4. Выходной алфавит абстрактного автомата содержит четыре
буквы: y
0
, y
1
, y
2
, y
3
. Сколько разных выходных слов может вырабо-
тать автомат при условии, что в выходном слове 2 раза встречают-
ся буквы y
0
, 4 раза буква y
1
, 3 раза буква y
2
и 1 раз буква y
3
?
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
