2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Забавная задачка (разложение шариков по ячейкам)
Сообщение28.06.2008, 16:18 
Интересная задачка появилась на одном из форумов:

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

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

 
 
 
 
Сообщение28.06.2008, 17:54 
Аватара пользователя
Похоже на кол-во перестановок с повторяющимися элементами.

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

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

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

 
 
 
 
Сообщение29.06.2008, 02:51 
Аватара пользователя
Равно коэффциенту при $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)}.$$

 
 
 
 
Сообщение29.06.2008, 07:09 
Аватара пользователя
А вообще ответ тут простой:
A002817(n+1) $=\frac{(n+1)(n+2)(n^2+3n+4)}8.$

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

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

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

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

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

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

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

 
 
 
 
Сообщение29.06.2008, 11:34 
Интересно, как это формула получена?

 
 
 
 
Сообщение29.06.2008, 17:56 
Аватара пользователя
Если и цвета, и ящики обозначить 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 и далее по ссылкам.

 
 
 
 
Сообщение29.06.2008, 20:36 
Спасибо :!:

 
 
 
 
Сообщение30.06.2008, 08:46 
Аватара пользователя
Сошлось с моим - сегодня в маршрутке около часа ехал.

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

 
 
 
 
Сообщение02.07.2008, 15:01 
Аватара пользователя
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 раз меньше - ясно почему, но немножко всё больше - тоже понятно.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group