Полиномиальные множества

Question

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

Пусть 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!/ х ₁ !х ₂ !х ₃ !... где x ₁ , x ₂ , x ₃ - группы дублированных букв.

исправление (ясность) -> у вас естьв общей сложности нм шаров.n шаров каждого цвета, где есть m цветов;отсюда вы случайным образом выбираете n из этих шариков с общим нм и помещаете их в k отдельных корзин.

Answer 1

Позвольте мне быть уверенным, что я правильно понял вопрос.У нас есть m цветов.У нас есть k корзины.Мы хотим выбрать n шары и поместить их в контейнеры.У нас достаточно шариков каждого цвета, и нам не нужно беспокоиться о том, чтобы у них кончился какой-либо конкретный цвет.

В этом случае проблема сводится к тому, сколько у нас есть n шариков m*k видов.(Вид определяется цветом и корзиной.) Существует стандартная хитрость для вычисления этого.Сначала давайте перечислим виды.Положи все шары первого вида.Тогда делитель.Тогда все шары второго рода.Тогда делитель.И так до тех пор, пока у нас не будет всех n шаров и k*m - 1 разделителей.Эта процедура полностью обратима, если мы берем n + k*m - 1 вещей подряд, выбираем n из них как шары, а остальные как делители, затем мы можем раскрасить шары и положить их в мусорные ведра, чтобы добраться до nшары m цветов в k корзинах.

Поэтому ответом будет choose(n + k*m - 1, n).

(Обратите внимание, что я пришел к этому рассуждению после того, как узнал ответ.Мой реальный путь к ответу был намного длиннее и сложнее.)

Answer 2

Я считаю, что вы можете рассматривать эту проблему как m независимых n-мультикомбинаций.

Таким образом, ответ: m * множественный выбор (n, k), где множественный выбор (a, b) = C (a + b -1, b).

---

Редактировать: предполагается, что вы спрашиваете о n шарах каждого цвета и размещаете все шарики по нм.