Перестановки с повторениями
Иногда требуется переставлять предметы, некоторые из которых неотличимы друг от друга. Рассмотрим такой вариант перестановок, который называется перестановками с повторениями.
Пусть имеется предметов 1-го типа, предмета 2-го, предметов k-го типа и при этом + +...+ = n. Количество разных перестановок предметов
Р( , , ... ) = (n!)/( ! !... !) (5)
Для обоснования ( 5 ) сначала будем переставлять n предметов в предположении, что они все различны. Число таких перестановок равно п!. Затем заметим, что в любой выбранной расстановке перестановка одинаковых предметов не меняет комбинации, аналогично перестановка одинаковых предметов также не меняет комбинации и т. д. Поэтому получаем выражение (5).
Пример. Найдем количество перестановок букв слова КОМБИНАТОРИКА. В этом слове 2 буквы к, 2 буквы о, 1 буква м, 1 буква б, 2 буквы и, 1 буква н, 2 буквы а, 1 буква т и 1 буква р.
Таким образом, число перестановок букв этого слова равно: Р(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. Выходной алфавит абстрактного автомата содержит четыре буквы: , , , . Сколько разных выходных слов может выработать автомат при условии, что в выходном слове 2 раза встречаются буквы , 4 раза буква , 3 раза буква и 1 раз буква ?
