Комбинаторика: размещение предметов по ячейкам с ограничения

[Enoid]

Здравствуйте!
Недавно столкнулся со следующей задачей: сколько существует вариантов размещения 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 иначе). И тогда нужно считать количество вершин этого местами обрезанного дерева.
Помогите, если знаете.

[LynxGAV]

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}$.

[maxal]

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

$$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$ предметов.

[RIP]

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

Enoid писал(а):

Хотелось бы получить какую-нибудь короткую и красивую формулу

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

[maxal]

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)}$$

[RIP]

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

[LynxGAV]

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

[maxal]

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

[LynxGAV]

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

[maxal]

Обозначение $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}$.

[LynxGAV]

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

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

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

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

[maxal]

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

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

[LynxGAV]

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

[maxal]

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

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