Дискретная математика. Ерош И.Л - 67 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

67
4.1.4. Перестановки с повторениями
Иногда требуется переставлять предметы, некоторые из которых
неотличимы друг от друга. Такой вариант перестановок называется пе
рестановками с повторениями.
Пусть имеется n
1
предметов 1го типа, n
2
предметов 2го типа,
n
k
предметов kго типа и при этом n
1
+ n
2
+ …+ n
k
= n.
Количество различных перестановок предметов определится формулой
12
123
12
!
,,,..., .
(!! !)
k
k
n
Pn n n n
nn n
3
4
(4.5)
Для обоснования (4.5) сначала будем переставлять все n предме
тов в предположении, что они все различные. Число таких переста
новок равно n!. Затем заметим, что в любой выбранной расстановке
перестановка n
1
одинаковых предметов не меняет комбинации, ана
логично перестановка n
2
одинаковых предметов также не меняет
комбинации и т. д. Поэтому получаем формулу (4.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. Выходной алфавит абстрактного автомата содержит 4 буквы: y
0
,
y
1
, y
2
и y
3
. Сколько разных выходных слов может выработать авто
мат при условии, что в выходном слове 2 раза встречается буква y
0
, 4
раза буква y
1
, 3 раза буква y
2
и 1 раз буква y
3
?

Страницы