Сочетания с повторениями
Пример. Требуется купить 7 пирожных. В магазине имеются пирожные следующих видов: эклеры, песочные, слоеные и наполеоны, Сколько вариантов выбора?
Решение: выбранные пирожные заменяем единицами, и добавляем три нуля (разделителя). Каждой перестановке однозначно соответствует некоторый выбор. Например, одному из вариантов покупки будет соответствовать такой код: 1101110101. Пирожные покупаются следующим образом. Количество единиц слева до первого нуля соответствует покупке эклеров, между первым и вторым нулем - покупке песочных, между вторым и третьим - покупке слоеных, единицы после третьего нуля соответствуют числу покупаемых наполеонов. В случае приведенного кода покупается 2 эклера, 3 песочных, 1 слоеное и 1 наполеон. Количество вариантов покупки пирожных равно числу перестановок из 7 объектов одного типа (единиц) и 3 объектов второго типа (нулей).
Если имеются предметы n разных типов (без ограничения числа предметов каждого типа) и требуется определить, сколько комбинаций можно сделать из них, чтобы в каждую комбинацию входило k предметов? Каждую комбинацию шифруем с помощью 0 и 1, причем 1 соответствуют предметам, а 0 выполняют функцию разделителей. Тогда записав k единиц и добавив n - 1 нуль, мы получим комбинацию, при которой выбираются k предметов первого типа и ни одного предмета остальных типов. Переставляя всеми способами эти k единиц и n - 1 нуль, мы будем каждый раз получать некоторую расстановку, состоящую из k предметов. Тогда
(8)
Упражнения
1. Входной алфавит абстрактного конечного автомата содержит 5 символов, например, Входные слова имеют длину в 11 символов. Сколько разных слов может быть подано на вход конечного автомата, если слова, имеющие одинаковый состав букв и различающиеся только порядком, считать одинаковыми? Например, слова и считаются одинаковыми. При решении задачи нужно учесть, что формула (8) определяет только количество вариантов выбора букв, но не их порядок в слове.
2. Граф-схема алгоритма микропрограммного автомата содержит операторные и условные вершины. Операторные вершины "начало" и "конец" обязательны. Сколько существует разных граф-схем алгоритмов, содержащих 6 вершин, если нас интересует только количественный состав, а не связи между вершинами?
