Генерирование комбинаторных объектов (часть 2)

В материале [https://dzen.ru/a/Y7VvO3pbCS6_qenS?share_to=link] читатель познакомился с четырьмя основными расчётными формулами (перестановка, размещения с повторениями, сочетание без повторений, сочетание с повторениями), позволяющими решать огромное число комбинаторных задач.

Продолжим изложение этого материала, а также раскроем несколько очень полезных свойств различных расчётных комбинаторных формул.

Так, например, с перестановками связано ещё одно определение: перестановки с повторениями. При выполнении Упражнений, представленных в [https://dzen.ru/a/Y7VvO3pbCS6_qenS?share_to=link] читатели могли заметить, что символы (цифры или буквы) могут повторяться, при этом считать одинаковые символы как разные совершенно некорректно.

Теорема о комбинаторном числе различных размещений элементов различных типов множества

Пример использования теоремы о перестановках с повторениями

Пример 7. Сколькими способами можно отправить 6 электронных писем, если имеются три различных электронных адреса, а каждое письмо можно отправить с любого из них?

Решение. Поскольку каждое из шести электронных писем можно отправить с любого из трёх электронных адресов, то комбинаторное число вариантов определяется числом размещений с повторениями из трёх по шесть, т.е. три в шестой степени.

Пример о комбинаторном числе всех подмножеств n-элементного множества

Для генерирования комбинаторных объектов путём генерации всех перестановок в лексикографическом порядке часто используется рекурсивный алгоритм, при этом идея рекурсии заключается в следующем: на i-й позиции должны побывать все элементы массива p с i-го по n-й и для каждого из этих элементов должны быть получены все перестановки остальных элементов, начиная с (i + 1)-го места, в лексикографическом порядке, а после получения последней из перестановок, начиная с (i + 1)-й позиции, исходный порядок элементов должен быть восстановлен.

В качестве Упражнения определите, различных слов можно получить перестановкой букв слова α? Варианты слов α и условий для перестановки букв в заданном слове α представлены в следующей таблице.

Варианты для самостоятельного решения

Пример решения 30-ого варианта:

Общее число различных слов, полученных перестановкой букв слова огород, равно числу перестановок с повторениями:

Если в каком-то слове все три буквы «о» стоят рядом, то тройную о можно считать единым символом, поэтому число слов, в которых три буквы о стоят рядом, равно Р4 = 4! = 24.

Таким образом, получаем общее число различных слов, в которых три буквы о не стоят рядом, равное 120 – 24 = 96.