Комбинаторные алгоритмы для программистов



   Информационные стенды настенные и напольные.            

Задачи - часть 2


Каждой перестановке соответствует распределение номеров мест на
k
классов. В первый класс попадают номера тех мест, на которые попали предметы первого типа, во второй - номера мест предметов второго типа и так далее. Тем самым устанавливается соответствие между перестановками с повторениями и раскладкой номеров мест по "ящикам". Понятно, что формулы решения задач оказались одинаковыми.

В рассмотренных задачах мы не учитывали порядок, в котором расположены элементы каждой части. В некоторых задачах этот порядок надо учитывать.

Задача 3. Флаги на мачтах.

Имеется

n
различных сигнальных флагов и
k
мачт, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке развешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?

Каждый способ развешивания флагов можно осуществить в два этапа. На первом этапе мы переставляем всеми возможными способами данные

n
флагов. Это можно сделать
n!
способами. Затем берем один из способов распределения
n
одинаковых флагов по
k
мачтам (число этих способов
C_{n+k-1}^{k-1}
). Пусть этот способ заключается в том, что на первую мачту надо повесить
n_1
флагов, на вторую -
n_2
флагов, ..., на
k
n_k
флагов, где
n_1 + n_2 + \ldots + n_k = n
. Тогда берем первые
n_1
флагов данной последовательности и развешиваем в полученном порядке на первой мачте; следующие
n_2
флагов развешиваем на второй мачте и т.д. Ясно, что используя все перестановки
n
флагов и все способы распределения
n
одинаковых флагов по
k
мачтам, получим все способы решения поставленной задачи. По правилу произведения получаем, что число способов развешивания флагов равно
n!C_{n+k-1}^{k-1}=\frac{{(n+k-1)!}}{{(k-1)!}}=A_{n+k-1}^n.

(5.3)

Вообще, если имеется
n
различных вещей, то число способов распределения этих вещей по
k
различным ящикам равно
A_{n+k-1}^n
.




Содержание  Назад  Вперед