2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Шарики и ящики
Сообщение26.12.2010, 11:22 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 12:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 12:18 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 12:25 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:20 
Заслуженный участник
Аватара пользователя


07/01/10
2015

(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 шара, в трёх остальных по одному.

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:27 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:32 
Заслуженный участник


27/04/09
28128
Мы имеем по $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|$?

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:50 
Заслуженный участник
Аватара пользователя


07/01/10
2015

(arseniiv)

arseniiv в сообщении #391792 писал(а):
Мы имеем по $p_i$ ящиков...

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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 13:56 
Заслуженный участник


27/04/09
28128
caxap в сообщении #391794 писал(а):
Не знаю, к чему такой формализм.
От выбора формализма зависит, получится какая-то ПФ или нет. :-) Правда, с моей стороны вряд ли что-то получится. Может, Zealint что-нибудь скажет когда-нибудь?..

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 18:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 18:34 
Заслуженный участник


27/04/09
28128
Даже если сахару ясно, мне не ясно. :-)

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 18:38 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории

(Оффтоп)

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

 Профиль  
                  
 
 Re: Шарики и ящики
Сообщение26.12.2010, 19:11 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group