Шарики и ящики

[caxap]

Сколько способов разложить $n$ белых и $m$ черных шариков в $p$ ящиков? (Ящики неразличимы. Пустым ящик быть не может.)

Подскажите, пожалуйста, куда думать. Если бы белые и чёрные шары были различимы между собой, то тогда бы были числа Стирлинга для подмножеств. Но тут уже не подходят.

[arseniiv]

Т. е. $p = m + n$? Или может быть меньше?

[caxap]

arseniiv, может и меньше. При $p=1$ и $p=m+n$ -- один способ. Может какую-то рекуррентность можно составить, только я не соображу никак.

[arseniiv]

Да, что-то я сразу не понял. Хотел подумать про производящую функцию последовательности выборок ящиков (по 1, по 2 и т. д.), но так можно было бы, если шары одного цвета! Не знаю, что делать с двумя видами шаров. Если попробовать связать две производящие функции друг с другом, одну для ящиков по белым шарам, другую по чёрным. Только не представляю, как вообще это сделать и легко ли будет решить.

-- Вс дек 26, 2010 15:30:52 --

Вот если были бы только белые шары, производящая функция последовательности по кол-ву шаров была бы $A(z) = (z + z^2 + z^3 + \ldots)^p = z^p (1 - z)^{-p}$, если не ошибся. Может, как-то её модифицировать можно, кто-нибудь знает?

[caxap]

(arseniiv)

arseniiv в сообщении #391755 писал(а):

$A(z) = (z + z^2 + z^3 + \ldots)^p = z^p (1 - z)^{-p}$

In[40]:= SeriesCoefficient[z^4 (1-z)^(-4),{z,0,5}]
Out[40]= 4

А на самом деле всего одно размещение: в одном ящике 2 шара, в трёх остальных по одному.

[ИСН]

caxap, а зачем тогда Вы начали говорить про числа Стирлинга? Ящики там неразличимы, но шары-то да.

[arseniiv]

Это я думал, что ящики пронумерованы.

-- Вс дек 26, 2010 16:27:21 --

Тогда надо подумать, как функцию состряпать.

[caxap]

ИСН
Шары различимы только по цвету. Все белые между собой и всё черные между собой неразличимы. А числа Стирлинга -- это единственное, что хоть издалека напоминает мою задачу: ведь если бы все шары были разных оттенков, то ответом бы были числа Стирлинга. Иногда в комбинаторных задачах помогает сначала сделать всё различным, а в конце поделить на что-нибудь, тем самым убирая различие. Но здесь так у меня не получается сделать.

[arseniiv]

Мы имеем по $p_i$ ящиков с $n_i$ белыми и $m_i$ чёрными шарами в них, причём $\left( \forall i \quad m_i, n_i, p_i \geqslant 1 \right) \wedge$$\sum_i {v_i} = v, \quad v \in \{m, n, p \}$. Так?

-- Вс дек 26, 2010 16:47:10 --

Давайте временно обозначим эти числа $R^p_{m, n}$? Видно, что это тоже самое, что $R^p_{n, m}$. Тогда, может, вместо $m$ и $n$ использовать $c = m + n$ и $d = \left| m - n \right|$?

[caxap]

(arseniiv)

arseniiv в сообщении #391792 писал(а):

Мы имеем по $p_i$ ящиков...

Не знаю, к чему такой формализм. Есть два цвета шаров, шары одного цвета неразличимы. Ящики неразличимы. Т. е. если есть 2 черных и 3 белых шара, а ящиков 3, то, например, разбиения "w,bwb,w" и "wbb,w,w" одинаковы, а "w,bwb,w" и "b,wwb,w" -- разные.

[arseniiv]

caxap в сообщении #391794 писал(а):

Не знаю, к чему такой формализм.

От выбора формализма зависит, получится какая-то ПФ или нет. Правда, с моей стороны вряд ли что-то получится. Может, Zealint что-нибудь скажет когда-нибудь?..

[ИСН]

caxap, Вам про один цвет всё ясно? Если бы только белые шары, скажем. Э?

[arseniiv]

Даже если сахару ясно, мне не ясно.

[ИСН]

(Оффтоп)

Тогда Вы можете пока почитать про http://mathworld.wolfram.com/PartitionFunctionP.html

[arseniiv]

И как увязать её с задачей? Что-то опять не додумаюсь.