2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Комбинаторика: размещение предметов по ячейкам с ограничения
Сообщение14.12.2007, 22:37 


14/12/07
24
Здравствуйте!
Недавно столкнулся со следующей задачей: сколько существует вариантов размещения n предметов (предметы одинаковые) в k ячеек так, чтобы в каждой ячейке было не более m предметов. Кому-нибудь приходилось сталкиваться с чем-либо подобным?
Хотелось бы получить какую-нибудь короткую и красивую формулу) (как например решение аналогичной задачи, но без последнего условия).
Пока я остановился на следующем: если обозначить искомое число за F(n,m,k), то имеет место рекурсивная формула F(n,m,k)=F(n,m,k-1)+F(n-1,m,k-1)+...+F(n-m,m,k-1). Можно получить и начальные значения (например F(x,m,1) = 1 если x<=m и 0 иначе). И тогда нужно считать количество вершин этого местами обрезанного дерева.
Помогите, если знаете.

 Профиль  
                  
 
 Re: Задача по комбинаторике
Сообщение15.12.2007, 02:16 
Заслуженный участник


28/10/05
1368
Enoid писал(а):
Здравствуйте!
Недавно столкнулся со следующей задачей: сколько существует вариантов размещения n предметов (предметы одинаковые) в k ячеек так, чтобы в каждой ячейке было не более m предметов. Кому-нибудь приходилось сталкиваться с чем-либо подобным?
Хотелось бы получить какую-нибудь короткую и красивую формулу) (как например решение аналогичной задачи, но без последнего условия).


Если без последнего условия (которое, как я поняла, "чтобы в каждой ячейке было не более m предметов"), то ответ будет $C_{k-1}^{n+k-1}$. Эту задачу можно решить, переформулировав условие: пусть даны n шаров, одинаковых (рисуем кружочки в линию), найти число способов, какими можно нарисовать (k-1) черточек между шарами (которые обозначают "коробки"; две черточки могут располагаться рядом, что значит, что коробка пустая).

Что касается задачи с условием, то эта задача сводится к следующей: сколько существует решений, не отрицательных, уравнения $x_1+x_2+\dots+x_k=n$ c условием $x_k \leqslant m$. [Она же: подсчет способов размещения n идентичных предметов по k ячейкам таким образом, чтобы в каждой было не более m предметов.]

Вот если бы условие было $x_k \geqslant m$, то достаточно положить m шариков в каждую коробку, каких k штук. То есть остается шариков $(n-km)$ cвободных для размещения и число способов: $C_{k-1}^{n-km+k-1}$.

Добавлено спустя 23 минуты 56 секунд:

Если $x_k \leqslant m$, то 1. считаем сколько существует способов разместить n идентичных предметов по k ячейкам: $C_{k-1}^{n+k-1}$; 2. надо вычесть случаи, в которых в одной из ячеек оказалось больше, чем m предметов. Есть k возможностей выбрать ячейку, в которой есть больше, чем m предметов, и, располагая в выбранную ячейку (m+1) предмет, остаются [n-(m+1)] предметов, которые надо разместить по k ячейкам, т.е. число способов: $k \ C_{k-1}^{n-(m+1)+k-1}$. 3. Ответ: $C_{k-1}^{n+k-1} \ - \ k \ C_{k-1}^{n-(m+1)+k-1}$.

 Профиль  
                  
 
 
Сообщение15.12.2007, 04:01 
Модератор
Аватара пользователя


11/01/06
5660
Принцип включений-исключений дает ответ:

$$F(n,m,k) = \sum_{j=0}^{\lfloor n/(m+1)\rfloor} (-1)^{j} {k\choose j} {n-(m+1)j+k-1\choose k-1}$$

здесь $j$ соответствует количеству ячеек, в которых больше $m$ предметов.

 Профиль  
                  
 
 
Сообщение15.12.2007, 04:07 
Заслуженный участник
Аватара пользователя


11/01/06
3822
LynxGAV
Твоё решение неверно, ведь те случаи размещения, в которых более чем в одну ячейку попадает более $m$ предметов, ты вычла несколько раз... (Да и аргументы у биномиальных коэффициентов перепутаны...) Если действовать таким путём, то надо пользоваться формулой включения-исключения, но вряд ли это удовлетворит автора треда:
Enoid писал(а):
Хотелось бы получить какую-нибудь короткую и красивую формулу

По сути дело сводится к вычислению коэффициента при $x^n$ в многочлене $(1+x+\ldots+x^m)^k$. Лично я очень сильно сомневаюсь в существовании подобной формулы, но я могу и ошибаться.

 Профиль  
                  
 
 
Сообщение15.12.2007, 04:48 
Модератор
Аватара пользователя


11/01/06
5660
RIP писал(а):
По сути дело сводится к вычислению коэффициента при $x^n$ в многочлене $(1+x+\ldots+x^m)^k$. Лично я очень сильно сомневаюсь в существовании подобной формулы, но я могу и ошибаться.

Ну это примерно дает ту же самую формулу, что и включения-исключения:
$$[x^n](1+x+\ldots+x^m)^k = [x^n] \left(\frac{1-x^{m+1}}{1-x}\right)^k = \sum_{j=0}^{\infty} [x^{j(m+1)}] (1-x^{m+1})^k\cdot [x^{n-j(m+1)}] (1-x)^{-k} =$$
$$= \sum_{j=0}^{\infty} (-1)^{n-jm} {k\choose j} {-k\choose n-j(m+1)} = \sum_{j=0}^{\lfloor n/(m+1)\rfloor} (-1)^j {k\choose j} {k+n-j(m+1)-1\choose n-j(m+1)}$$

 Профиль  
                  
 
 
Сообщение15.12.2007, 05:22 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Это понятно. Под "подобной" формулой я подразумевал "короткую и красивую".

 Профиль  
                  
 
 
Сообщение15.12.2007, 13:54 
Заслуженный участник


28/10/05
1368
RIP, формула, которую я привела верна для частного случая, когда положив m+1 предмет в одну из возможных ячеек, число оставшихся предметов меньше, чем m+1 и их можно раскладывать как угодно. Пробежала глазами, но ничего не заметила, ткните носом, в каком месте перепутаны индексы :D.

 Профиль  
                  
 
 
Сообщение15.12.2007, 14:03 
Модератор
Аватара пользователя


11/01/06
5660
LynxGAV, обозначение $C_n^m$ соответствует обозначению ${n\choose m}$, а у вас индексы переставлены наоборот: верхний индекс стоит снизу, а нижний сверху. :D

 Профиль  
                  
 
 
Сообщение15.12.2007, 14:06 
Заслуженный участник


28/10/05
1368
Я не помню, как нас учили, но такие обозначения встречала и не раз..

 Профиль  
                  
 
 
Сообщение15.12.2007, 14:11 
Модератор
Аватара пользователя


11/01/06
5660
Обозначение $C_n^m$ сейчас считается устаревшим. Почти во всех современных текстах используется ${n\choose m}$. Но как бы там ни было, размер множества у $C$ должен стоять снизу, а размер выборки - сверху.

То есть вместо вашего $C_{k-1}^{n+k-1}$ должно быть $C_{n+k-1}^{k-1}$ (если вы хотите использовать $C$) или ${n+k-1\choose k-1}$.

 Профиль  
                  
 
 
Сообщение15.12.2007, 14:44 
Заслуженный участник


28/10/05
1368
Ей-богу не пойму, почему Вы на меня наехали :D. Даже посмотрела две книги по теор. веру, и обозначения точно такие, как у меня.

$C_k^n \ = {n\choose k}$ !

Добавлено спустя 15 минут 46 секунд:

Обозначение $C_n^k$ встречается в русских учебниках, вот и вся проблема.

 Профиль  
                  
 
 
Сообщение15.12.2007, 14:49 
Модератор
Аватара пользователя


11/01/06
5660
А мы на каком языке общаемся? :lol:
Оно не просто встречается, оно общепринято. Вот например:
http://kvant.mccme.ru/1973/02/binomialn ... _mnogo.htm

Таким образом, ваши пусть даже книжные обозначения идут вразрез с общепринятыми.

 Профиль  
                  
 
 Эти обозначения из иностранной литературы.
Сообщение15.12.2007, 15:02 
Заслуженный участник


28/10/05
1368
Простите, но я впервые о биноминальных коэффициентах не из Кванта узнала... Правда и не из Википедии, но она является подтверждением того, что такие обозначения общеприняты.

 Профиль  
                  
 
 
Сообщение15.12.2007, 15:09 
Модератор
Аватара пользователя


11/01/06
5660
Возможно, что и общеприняты, но не в русской литературе. Русская википедия, кстати, это подтверждает.

В общем, чтобы не было разночтений, лучше использовать ${n\choose m}$, тем более что сейчас именно это обозначение наиболее употребимо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

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



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

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


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

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