Полиномиальные множества
У меня проблема с выяснением этой проблемы, она похожа на объединение наборов неуникальных букв, но немного отличается.
Пусть k, m и n - натуральные числа. У нас есть NM шаров, m цветов, n шаров и k бункеров с уникальной маркировкой. Сколько существует способов выбрать n шаров, чтобы положить их в k пакетов?
Например, если m = 3, n = k = 2, результат равен 21. Есть 3 цвета, в которых мы выбираем 2 шарика из общего количества 6, чтобы разместить их в 2 ячейках.
(-, WW), (-, WR), (-, WB)...
(WW, -), (WR, -)...
(W, W), (W, R)...
(B, W), (B, R)...
Обычная версия этой проблемы не требует выбора подмножества общих элементов. Эта проблема дает n! / х1! х2! х3!... где x1, x2, x3 - группы дублированных букв.
исправление (ясность) -> у вас есть общее количество шаров нм. n шаров каждого цвета, где есть m цветов; отсюда вы случайным образом выбираете n из этих шариков из общего количества нм и помещаете их в k отдельных корзин.
2 ответа
Позвольте мне быть уверенным, что я правильно понял вопрос. У нас есть m цвета. У нас есть k бункера. Мы хотим выбрать n шары и поместите их в контейнеры. У нас достаточно шариков каждого цвета, и нам не нужно беспокоиться об их отсутствии
В этом случае проблема сводится к тому, сколько у нас есть способов n шары m*k виды. (Вид определяется цветом и корзиной.) Существует стандартная хитрость для вычисления этого. Сначала давайте перечислим виды. Положи все шары первого вида. Затем делитель. Тогда все шары второго рода. Затем делитель. И так до тех пор, пока у нас все n шары и k*m - 1 делители вниз. Эта процедура полностью обратима, если мы примем n + k*m - 1 вещи подряд n из них, чтобы быть шарами, а остальные, чтобы быть разделителями, мы можем затем раскрасить шары и положить их в мусорные ведра, чтобы добраться до n шары m цвета в k бункера.
Поэтому ответ choose(n + k*m - 1, n),
(Обратите внимание, что это и есть причина, по которой я пришел после того, как узнал ответ. Мой реальный путь к ответу был намного длиннее и сложнее).
Я считаю, что вы можете рассматривать эту проблему как m независимых n-мультикомбинаций.
Таким образом, ответ m * multihoose(n, k), где multihoose(a, b) = C(a + b -1, b).
Редактировать: Предполагается, что вы спрашиваете о n шариков каждого цвета и размещаете все шарики по нм.