2014 dxdy logo

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

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




 
 Комбинаторика: размещение предметов по ячейкам с ограничения
Сообщение14.12.2007, 22:37 
Здравствуйте!
Недавно столкнулся со следующей задачей: сколько существует вариантов размещения 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 
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 
Аватара пользователя
Принцип включений-исключений дает ответ:

$$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 
Аватара пользователя
LynxGAV
Твоё решение неверно, ведь те случаи размещения, в которых более чем в одну ячейку попадает более $m$ предметов, ты вычла несколько раз... (Да и аргументы у биномиальных коэффициентов перепутаны...) Если действовать таким путём, то надо пользоваться формулой включения-исключения, но вряд ли это удовлетворит автора треда:
Enoid писал(а):
Хотелось бы получить какую-нибудь короткую и красивую формулу

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

 
 
 
 
Сообщение15.12.2007, 04:48 
Аватара пользователя
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 
Аватара пользователя
Это понятно. Под "подобной" формулой я подразумевал "короткую и красивую".

 
 
 
 
Сообщение15.12.2007, 13:54 
RIP, формула, которую я привела верна для частного случая, когда положив m+1 предмет в одну из возможных ячеек, число оставшихся предметов меньше, чем m+1 и их можно раскладывать как угодно. Пробежала глазами, но ничего не заметила, ткните носом, в каком месте перепутаны индексы :D.

 
 
 
 
Сообщение15.12.2007, 14:03 
Аватара пользователя
LynxGAV, обозначение $C_n^m$ соответствует обозначению ${n\choose m}$, а у вас индексы переставлены наоборот: верхний индекс стоит снизу, а нижний сверху. :D

 
 
 
 
Сообщение15.12.2007, 14:06 
Я не помню, как нас учили, но такие обозначения встречала и не раз..

 
 
 
 
Сообщение15.12.2007, 14:11 
Аватара пользователя
Обозначение $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 
Ей-богу не пойму, почему Вы на меня наехали :D. Даже посмотрела две книги по теор. веру, и обозначения точно такие, как у меня.

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

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

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

 
 
 
 
Сообщение15.12.2007, 14:49 
Аватара пользователя
А мы на каком языке общаемся? :lol:
Оно не просто встречается, оно общепринято. Вот например:
http://kvant.mccme.ru/1973/02/binomialn ... _mnogo.htm

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

 
 
 
 Эти обозначения из иностранной литературы.
Сообщение15.12.2007, 15:02 
Простите, но я впервые о биноминальных коэффициентах не из Кванта узнала... Правда и не из Википедии, но она является подтверждением того, что такие обозначения общеприняты.

 
 
 
 
Сообщение15.12.2007, 15:09 
Аватара пользователя
Возможно, что и общеприняты, но не в русской литературе. Русская википедия, кстати, это подтверждает.

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

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


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