Помогите разобраться с задачкой. Комбинаторика

[Ratix]

Имеется $n_1$ шаров красного цвета, $n_2$ шаров синего цвета, ..., $n_k$ шаров k-го цвета. Чему равно число способов распределения этих шаров по m одинаковым урнам?

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

Решение для пронумерованных урн :
N - число вариантов.
Распределим $n_1$ красных шаров по m урнам - $C_{n_1+m-1}^{n_1}$. Тоже самое получим для шаров любого цвета - $C_{n_k+m-1}^{n_k}$
Отсюда $N = C_{n_1+m-1}^{n_1}C_{n_2+m-1}^{n_2}\cdot...\cdot C_{n_k+m-1}^{n_k}$

Но как связать это решение с задачей о одинаковых урнах?

[Brukvalub]

Может, сначала перемнумеровать урны и решить задачу, а потом "стереть" нумерацию, считая за один те различные случаи, которые переходят друг в друга просто изменением номеров урн?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

1. Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

2. Приведите свои попытки решения и/или укажите затруднения, уже можно.

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

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Ratix]

Brukvalub в сообщении #926535 писал(а):

Может, сначала перемнумеровать урны и решить задачу, а потом "стереть" нумерацию, считая за один те различные случаи, которые переходят друг в друга просто изменением номеров урн?

Звучит это конечно замечательно, только вот как "стереть" эту самую нумерацию.

[Brukvalub]

Так я в своем сообщении написал, как стереть нумерацию.

[Ratix]

Brukvalub в сообщении #927151 писал(а):

Так я в своем сообщении написал, как стереть нумерацию.

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

[provincialka]

Brukvalub, не уверена, что так легко "стереть номера". Например, распределение (КК, СС) парное к распределению (СС, КК) и при стирании номеров они превращаются в одно. Но распределение (КС, КС) при такой перестановке переходит само в себя.

[arseniiv]

Ответом будет коэффициент при $x^m$ в $(x^0+x^1+\ldots+x^{n_1})\cdots(x^0+x^1+\ldots+x^{n_k})$.

Причина: $x^m$ встречается в сумме столько раз, сколько раз числа $(i_1,\ldots,i_k)\in0..n_1\times\ldots\times0..n_k$ складываются в $m$ (взяли по $i_s$ шаров цвета $s$).

Таким же способом можно узнать число способов набрать $n$ шаров с другим «репертуаром» (например, красных надо взять непременно не меньше двух; или синих чётное число; или каких-то бесконечно много).

[Ratix]

arseniiv, Вы не могли бы пояснить что это за разложение и что вы обозначаете за $x$?

[VAL]

Ratix в сообщении #927594 писал(а):

arseniiv, Вы не могли бы пояснить что это за разложение и что вы обозначаете за $x$?

Это не разложение. Это производящая функция. А $x$ - переменная. Нас интересует не $x$, а коэффициент при нужной степени.

PS: Причем, как верно указал patzer2097, производящая функция для другой задачи.

[patzer2097]

arseniiv, по-моему, Ваши решение и ответ подходят для другой задачи: "Сколько существует способов выбора $m$ шаров из $n_1$ шаров цвета 1, ..., $n_k$ цвета $k$?"

А что касается задачи ТС, то при $k=1$ она равносильна следующей: сколько существует способов представить число $n$ в виде суммы не более, чем $m$ слагаемых (с точностью до порядка этих слагаемых). И тогда искомое число будет коэффициентом при $x^m$ в разложении

$$\prod\limits_{t=1}^m\frac{1}{1-x^t},$$

в чем можно убедиться непосредственно, если заметить, что слагаемое $x^{a_1\cdot1}\ldots x^{a_m\cdot m}$ соответствует тому разбиению, когда ровно $a_t$ корзин содержат не менее $t$ шаров.

При $k=2$ все усложняется еще больше, и тут мне нечего Вам посоветовать.

[arseniiv]

(Оффтоп)

Чёрт, если я даже после трёх проверок промазал, то, похоже, мне надо на время не отвечать.

Надеюсь, ТС простит…

(Дошло!)

Я опять подумал, что в каждой урне должен быть ровно один шар (в прошлый раз нагородил с комбинаторикой по тому же поводу — теперь заодно стало спокойнее: хотя бы одинаковые ошибки, а не разные). Вот балда.