Забавная задачка (разложение шариков по ячейкам)

[venja]

Интересная задачка появилась на одном из форумов:

5 белых шариков, 5 черных и 5 красных надо разложить по
3 ящикам так, чтобы в каждом ящике оказалось по 5 шариков.
Сколькими способами это можно осуществить?

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

[Trotil]

Похоже на кол-во перестановок с повторяющимися элементами.

[Батороев]

Если белые шарики обозначить через $ 0 $, черные - через $ 1 $, а красные - через $ 2 $. Тогда, по-видимому, можно будет перейти к рассмотрению количества троек пятизначных чисел в троичной системе счисления, у которых в сумме кол-во каждой из цифр $ 0, 1, 2 $ ограничено числом $ 5 $.

[ewert]

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

---------------------------------
Кстати, а задачку лучше ставить не для 5+5+5, а для 7+7+7. Ответ просто зверский!

[maxal]

Равно коэффциенту при $u^5 v^5 w^5 x^5 y^5 z^5$ в разложении

$$\frac{1}{(1-ux)(1-uy)(1-uz)(1-vx)(1-vy)(1-vz)(1-wx)(1-wy)(1-wz)}.$$

[maxal]

А вообще ответ тут простой:
A002817(n+1) $=\frac{(n+1)(n+2)(n^2+3n+4)}8.$

Соответственно, для $n=3$ получаем число $55$.

[venja]

Утверждается, что ответ другой. Ответ вроде бы есть, но без решения.

[maxal]

Ну тут есть еще варианты с различимостью/неразличимостью ящиков. Тот, что я привел выше, - для различимых ящиков.

Добавлено спустя 1 час 34 минуты 11 секунд:

maxal писал(а):

А вообще ответ тут простой:
A002817(n+1) $=\frac{(n+1)(n+2)(n^2+3n+4)}8.$

Соответственно, для $n=3$ получаем число $55$.

Тьфу, нам нужно число вариантов для $n=5$, а это $231$.

[venja]

Интересно, как это формула получена?

[maxal]

Если и цвета, и ящики обозначить 1,2,3 и положить $x_{ij}$ количеству шариков цвета $i$ в ящике номер $j$, то каждая раскладка шариков по ящикам будет соответствовать полу-магическому квадрату размера $3\times 3$:

$$\begin{bmatrix} x_{11} & x_{12} & x_{13}\\ x_{21} & x_{22} & x_{23}\\ x_{31} & x_{32} & x_{33} \end{bmatrix}$$

в котором сумма элементов каждой строки и каждого столбца равна $n$.
Ну а количество таких полу-магических квадратов - это классический результат - см. например: http://arxiv.org/abs/math.CO/0201013 и далее по ссылкам.

[venja]

Спасибо

[bot]

Сошлось с моим - сегодня в маршрутке около часа ехал.

Идея примерно та же. Это число всех матриц $2\times 2$ с целыми неотрицательными членами, с суммой элементов в любой строке (столбце), не превосходящей n и с общей суммой, не меньшей n.
От последнего условия освобождаемся, так как лишние легко учитываются. Полученное считаем, разбивая на случаи по максимальному из двух элементов на главной диагонали.

[bot]

maxal писал(а):

Ну тут есть еще варианты с различимостью/неразличимостью ящиков. Тот, что я привел выше, - для различимых ящиков.

Для неразличимых ящиков:

$$\frac{(n+1)(n+2)(n^2+3n+4)}{48} + R \ \ $$

,

где

$$\ \ R=\left\{\begin {array}{ll}\frac{(n+2)(n+4)}{16}+\frac{1}{3}\ , & \ \ n\equiv 0 \pmod 6 \\ \frac{(n+2)(n+4)}{16} \ , & \ \ n\equiv 2,4 \pmod 6 \\ \frac{n^2-1}{16} \ , & \ \ n\equiv 1,5 \pmod 6 \\ \frac{n^2-1}{16}+\frac{1}{3} \ , & \ \ n\equiv 3 \pmod 6 \\ \end{array} \right.$$

В частности для $n=5$ получается $40$.

Считается простым сведением к различимым. Грубо говоря, ответ в 6 раз меньше - ясно почему, но немножко всё больше - тоже понятно.