Составители:
Рубрика:
14
1.8. Сочетания с повторениями
П р и м е р. Требуется купить 7 пирожных. В магазине имеются
пирожные следующих видов: эклеры, песочные, слоеные и наполеоны.
Сколько вариантов выбора? Решение: выбранные пирожные заменяем
единицами, и добавляем три нуля (разделителя). Каждой перестановке
однозначно соответствует некоторый выбор. Например, одному из ва-
риантов покупки будет соответствовать такой код: 1101110101. Пиро-
жные покупаются следующим образом. Количество единиц слева до
первого нуля соответствует покупке эклеров, между первым и вторым
нулем – покупке песочных, между вторым и третьим – покупке слое-
ных, единицы после третьего нуля соответствуют числу покупаемых
наполеонов. В случае приведенного кода покупается 2 эклера, 3 песоч-
ных, 1 слоеное и 1 наполеон. Количество вариантов покупки пирожных
равно числу перестановок из 7 объектов одного типа (единиц) и 3 объек-
тов второго типа (нулей).
Если имеются предметы n разных типов (без ограничения числа
предметов каждого типа) и требуется определить, сколько комбинаций
можно сделать из них, чтобы в каждую комбинацию входило k предме-
тов? Каждую комбинацию шифруем с помощью 0 и 1, причем 1 соот-
ветствуют предметам, а 0 выполняют функцию разделителей. Тогда
записав k единиц и добавив n – 1 нуль, мы получим комбинацию, при
которой выбираются k предметов первого типа и ни одного предмета
остальных типов. Переставляя всеми способами эти k единиц и n – 1
нуль, мы будем каждый раз получать некоторую расстановку, состоя-
щую из k предметов. Тогда
P(k, n – 1) = (k + n – 1)!/(k!(n – 1)!) =
1
k
nk
C
+−
. (8)
Упражнения
1. Входной алфавит абстрактного конечного автомата содержит 5
символов, например, a, b, c, d, f. Входные слова имеют длину в 11 сим-
волов. Сколько разных слов может быть подано на вход конечного ав-
томата, если слова, имеющие одинаковый состав букв и различающие-
ся только порядком, считать одинаковыми? Например, слова baabcf и
fabcba считаются одинаковыми. При решении задачи нужно учесть,
что формула (8) определяет только количество вариантов выбора букв,
но не их порядок в слове.
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
