Главная > Математика > Дискретная математика. Алгоритмы и программы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.8. Перестановки с повторениями, мультимножества

Задача формулируется следующим образом. Имеются предметы различных видов. Сколько существует перестановок из элементов первого типа, элементов второго типа и т. д. элементов типа? Рассмотрим, например, мультимножество в котором содержатся 3 элемента а, 2 элемента элемент с и 4 элемента Мультимножество — это то же самое, что и множество, но в нем могут содержаться одинаковые элементы. Повторения элементов можно указать и другим способом: Таким образом, искомые перестановки с повторениями — это перестановки элементов мультимножества. Если бы мы рассматривали все элементы множества как различные, обозначив их то получили бы 10! перестановок, но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка множества Мвстретилась бы ровно поскольку в любой перестановке индексы при буквах а можно расставить 3! способами, при способами, при с — одним способом, а при соответственно 4! способами. Поэтому число перестановок множества Мравно . В применении к общему случаю те же рассуждения показывают, что число перестановок любого мультимножества (перестановки с повторениями) равно полиномиальному коэффициенту

где общее число элементов.

Перестановки с повторениями имеют тесную связь с сочетаниями. Определим количество этих перестановок следующим образом. Из всех мест перестановки место занимают элементы первого типа. Выбор мест для них можно сделать Сспособами. Из оставшихся мест элементы второго типа занимают места, которые можно выбрать способами. Те же рассуждения показывают, что элементы типа можно расположить в перестановке способами. Согласно правилу

прямого произведения, число перестановок с повторениями равно

Задача. Сколько существует различных перестановок из букв слова «Уссури»?

Решение.

<< Предыдущий параграф Следующий параграф >>
Оглавление