Разбиение [Комбинаторика]

[Whitaker]

Здравствуйте!
Попалась следующая задачка я ее вроде решил, но ответ в книжке отсуствует.
Хотелось бы проверить свой ответ.
Формулировка задачи: Найдите число способов разбить $n$ различных предметов на $r$ (некоторых, быть может, пустых) классов так, чтобы в точности $m$ классов содержало по $k$ предметов?
Решение задачи:
Пусть у нас есть множество $A=\{a_1, a_2,...,a_n\}$.
И по условию задачи у нас есть $r$ классов и также $m$ классов из $r$ должны быть заполнены полностью до $k$ элементов.
Выбрать $m$ классов из $r$ можно $C_{r}^{m}$ способами.
Теперь разложим все $n$ предметов в ряд и занумеруем их сверху. Получим перестановку с повторениями из $k$ единиц, $k$ двоек, ..., $k$ $m$-ок, а остальные $(n-km)$ элементов обозначим через нули.
А число таких перестановок равно $P(\underbrace{k,k, ....,k}_{m}, n-km)=\dfrac{n!}{(k!)^m(n-km)!}$.
Теперь осталось распределить $(n-km)$ различных предметов между оставшимимся $(r-m)$ классами. Это можно реализовать $C_{r+n-1-m(k+1)}^{r-m-1}$ способами.
По принципу произведения получим общий ответ к задаче:
$\dfrac{n!}{(k!)^m(n-km)!}C_{r}^{m}C_{r+n-1-m(k+1)}^{r-m-1}$

Я вроде полностью написал решение задачки.
Посмотрите пожалуйста правильно ли я решил задачу?

[svv]

А вдруг какой-то класс из $(r-m)$ оставшихся тоже после заполнения будет содержать ровно $k$ элементов? Тогда ведь нарушится условие, что "в точности $m$ классов ...".

[Whitaker]

Интересный Вы вопрос задали кстати

-- Пн окт 17, 2011 21:02:59 --

Буду думать

-- Пн окт 17, 2011 21:09:20 --

Пришла следующая мысль, но не знаю правильная она или нет.
Ведь по формуле включений-исключений можно найти количество целых неотрицательных решений уравнения $x_1+x_2+...+x_{r-m}=n-km$, где $x_i \neq k$ для любого $i$

-- Пн окт 17, 2011 21:35:35 --

Нам нужно найти число целых неотрицательных решений уравнения $x_1+x_2+...+x_{r-m}=n-km$ где $x_i \neq k$ для любого $i$.
Положим для удоства $r-m=N, n-km=M$
$N(\overline{x_1=k}, \overline{x_2=k}, ...., \overline{x_N=k})$-количество решений $(x_1, x_2, ..., x_N)$, где ни один из них равен $k$.
Тогда по формуле включений и исключений получим:
$N(\overline{x_1=k}, \overline{x_2=k}, ...., \overline{x_N=k})=N-N(x_1=k)-N(x_2=k)-...-N(x_N=k)+N(x_1=k, x_2=k)+...+N(x_{N-1}=k, x_N=k)-....+(-1)^NN(x_1=k, x_2=k, ..., x_N=k)$.
P.S. Хотя мне кажется, что предложенная мной идея довольно нехорошая.

[Whitaker]

Буду рад если кто-нибудь поделится идеей.

[PAV]

Мне кажется, что решение через формулу включений-исключений нормальное, и я что-то не уверен, что можно придумать что-нибудь проще и короче. То есть первый шаг такой, который и сделан, после которого задача сведена к тому, чтобы разложить заданные предметы по классам так, чтобы ни один класс не содержал в точности $k$ предметов. А эту последнюю задачу - уже через включения-исключения.

[VAL]

Просмотрел по диагонали. Сразу бросилось в глаза следущее:

Whitaker в сообщении #493587 писал(а):

Формулировка задачи: Найдите число способов разбить $n$ различных предметов на $r$ (некоторых, быть может, пустых) классов так, чтобы в точности $m$ классов содержало по $k$ предметов?
Решение задачи:
[..]
Теперь осталось распределить $(n-km)$ различных предметов между оставшимимся $(r-m)$ классами. Это можно реализовать $C_{r+n-1-m(k+1)}^{r-m-1}$ способами.

Вы используете формулу сочетаний с повторениями. Но ведь по условию различны предметы, распределяемые на классы, а не классы.

[Whitaker]

VAL в сообщении #493830 писал(а):

Просмотрел по диагонали. Сразу бросилось в глаза следущее:

Whitaker в сообщении #493587 писал(а):

Формулировка задачи: Найдите число способов разбить $n$ различных предметов на $r$ (некоторых, быть может, пустых) классов так, чтобы в точности $m$ классов содержало по $k$ предметов?
Решение задачи:
[..]
Теперь осталось распределить $(n-km)$ различных предметов между оставшимимся $(r-m)$ классами. Это можно реализовать $C_{r+n-1-m(k+1)}^{r-m-1}$ способами.

Вы используете формулу сочетаний с повторениями. Но ведь по условию различны предметы, распределяемые на классы, а не классы.

Согласен с Вами VAL, сделал грубую ошибку.
А как исправить?

-- Вт окт 18, 2011 16:52:44 --

Наверное нужно сделать так:
Полученный результат $C_{r+n-1-m(k+1)}^{r-m-1}$ умножить на $P_{n-km}=(n-km)!$ и разделить на $P_{n_1}P_{n_2}...P{n_{r-m}}$, где $n_1$ - число элементов в первом классе, ...., $n_{r-m}$-число элементов в $(r-m)$-м классе и $n_1+n_2+..+n_{r-m}=n-km$

-- Вт окт 18, 2011 16:56:45 --

Я правильно сказал?

[PAV]

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

[Whitaker]

Согласен с PAV. Думаю, что классы тоже различны между собой.
Тогда ответ должен быть такой как я написал выше.
Полученный результат $C_{r+n-1-m(k+1)}^{r-m-1}$ умножить на $P_{n-km}=(n-km)!$ и разделить на $P_{n_1}P_{n_2}...P{n_{r-m}}$, где $n_1$ - число элементов в первом классе, ...., $n_{r-m}$-число элементов в $(r-m)$-м классе и $n_1+n_2+..+n_{r-m}=n-km$

[VAL]

Whitaker в сообщении #493840 писал(а):

Наверное нужно сделать так:
Полученный результат $C_{r+n-1-m(k+1)}^{r-m-1}$ умножить на $P_{n-km}=(n-km)!$ и разделить на $P_{n_1}P_{n_2}...P{n_{r-m}}$, где $n_1$ - число элементов в первом классе, ...., $n_{r-m}$-число элементов в $(r-m)$-м классе и $n_1+n_2+..+n_{r-m}=n-km$

А где Вы возьмете числа $n_1, n_2, \dots n_{r-m}$? Ведь известна только их сумма.