Перестановки с повторениями
   Иногда требуется переставлять предметы, некоторые из которых неотличимы друг от друга. Рассмотрим такой вариант перестановок, который называется перестановками с повторениями.
    Пусть имеется     предметов 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 раз буква     ?

Закрыть