Помогите решить комбинаторную задачу

[Nub]

В общем виде условие такое:
Имеется N объектов, относящихся к L сортам. Количество объектов каждого сорта известно и равно $k_1, k_2, ..., k_L$,
$\sum{k_i}=N$
Определить число различных сочетаний по M объектов из N, $1\leM\leN$, если объекты, относящиеся к одному сорту,
считаются неразличимыми между собой.

Пример:
N=4, L=2, $k_1=3, k_2=1$, M=3, например, имеем 3 белых шара и 1 красный. Число сочетаний по 3 из 4 равно в данном случае 2 -
(Б, Б, Б) и (Б, Б, К).

В чём проблема:
Известные мне комбинаторные формулы не дают результата, например, $C^3_4=4$, в ней же все объекты считаются разными,
а у меня 3 белых шара между собой неразличимы. Число сочетаний с повторениями тоже пробовал - безрезультатно.

Я знаю формулу для числа различных перестановок на множестве из n элементов, среди которых имеется
$k_i$ элементов i-го вида: $\frac{n!}{k_1!\cdot ... \cdot k_n!}$, но для моего случая ничего похожего не нашёл.

P.S. Прошу прощения, если что-то не по правилам, я старался, даже проверил орфографические ошибки!
Помогите плиз, препод меня сожрёт иначе

[PAV]

Nub в сообщении #487691 писал(а):

Я знаю формулу для числа различных перестановок на множестве из n элементов, среди которых имеется
$k_i$ элементов i-го вида: $\frac{n!}{k_1!\cdot ... \cdot k_n!}$, но для моего случая ничего похожего не нашёл.

А чем этот случай отличается от Вашего?

[Nub]

PAV писал(а):

А чем этот случай отличается от Вашего?

Хотя бы тем, что $\frac{4!}{3!\cdot1!}=4$, а у меня всего 2 сочетания при этих данных. Это формула для перестановок, наверное, в ней существенен порядок объектов, а у меня нет. Лучше объяснить не могу

[PAV]

А, понял, невнимательно прочел условие задачи. Тогда да, отличается.

[Sonic86]

Обозначьте переменной $x_j$ количество элементов $j$-го сорта и переформулируйте задачу в виде системы диофантовых ограничений.

(если уж совсем не получается)

Задачу можно сформулировать так: найти число решений уравнения
$x_1+...+x_L=M, x_1 \leqslant k_1, ... , x_s \leqslant k_s$.
Формула для числа решений выводится индуктивно.

[Whitaker]

Согласен с Sonic86!
Так даже удобнее и понятнее.

[Nub]

Sonic86 в сообщении #487724 писал(а):

переформулируйте задачу в виде системы диофантовых ограничений.

Спасибо за совет, ключевые слова Вы дали, я попробую... но получается что прямой формулы нет в принципе? Мне-то это дали по дискретке...

[Nub]

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

Так даже удобнее и понятнее.

Нашёл, что диофантово уравнение $x_1 + ... + x_L = M$ имеет
$C^{L-1}_{M-1}$ различных решений в натуральных числах.
В принципе, логично, в формуле не должно быть N, ведь всё равно, из какого числа одинаковых объектов выбираем.
Но опять не сходится - например, имеем 3 белых шара, 2 синих, выбираем 2
(L=2, M=2, формула даёт $C_1^1$, на самом деле ответ = 3 (ББ, БС, СС).
Что я делаю не так, надо ещё как-то ограничения учесть?

[Sonic86]

Ну ладно, можно писать явно:
$x_1+...+x_L=M, x_1 \leqslant k_1, ... , x_s \leqslant k_s$
$N(F(x_1,...,x_s)=0)$ - число решений уравнения $F=0$
$N(x_1+...+x_L=M,x_1 \leqslant k_1, ... , x_s \leqslant k_s)=$
$N(x_1+...+x_{L-1}=M-x_L,x_1 \leqslant k_1, ... , x_s \leqslant k_s) =$
$\sum\limits_{A=0}^{\min \{ M,k_s\}} N(x_1+...+x_{L-1}=A,x_1 \leqslant k_1, ... , x_{s-1} \leqslant k_{s-1})$ - рекуррентная формула. Надо с ней чего-нибудь похимичить. Например, сгруппировать $k_j=1$, потом $k_j=2$,...
Так что теперь препод Вас если сожрет, то не так быстро

[Nub]

Nub в сообщении #487791 писал(а):

Что я делаю не так, надо ещё как-то ограничения учесть?

Что я делаю не так, понял ещё вчера.
Я не учёл случая, когда какого-то вида нет в наборе, для него формула будет
$C^{L-1}_{M+L-1}$
Но это, фактически, то же сочетание с повтореиями, а оно не подходит.
Теперь наверняка не учтутся случаи, если шаров какого-то вида "не хватит", ограничения сверху...

Например,
3 белых 2 синих выбираем 2
L=2 M=2
$C^1_3 = 3$
Верно

3 белых 1 синий
L=2 M=3
$C^1_4=4$
Это потому, что посчитались и те комбинации, для которых не хватит шаров:
ББС
БББ
БCC
ССС
Неверно

2 Sonic86 - спасибо, попробую ещё так, мне к понедельнику надо край сделать...

[PAV]

Простой замкнутой формулы тут не будет. Можно написать сложную формулу с какими-нибудь вложенными суммами, вычисление которой будет по сути мало отличаться от перебора вариантов. Можно сделать через производящие функции (по сложности практического вычисления - то же самое).
Для практического вычисления с конкретными числами можно считать рекуррентно, поочередно исключая классы один за другим.

[Null]

Обычно это решают при помощи включений-исключений.
Нам преподаватель засчитывал получившуюся сумму C.