Задачка по комбинаторике

[Zazaqa]

Сама задача:

$n$ людей разбили на $m$ групп поровну. Если поровну не получается, то в некоторых группах будет на 1 человека больше, чем в других. Теперь надо выбрать $k$ людей максимум по одному из каждой группы. Сколькими способами можно это сделать?

Решение:

Понятно, что при $k > m$ нельзя подобрать такую группу, то есть число способов равно 0.
Далее, при $k = m$ это просто $n_1^{m_1} \cdot n_2^{m_2}$, где $n_1, n_2$ - число людей в группах (с числом человек и числом человек плюс один), а $m_1, m_2$ - число групп с числом человек и числом человек плюс один соответственно.
Далее, если получилось, что поделились идеально поровну (без остатка), то $C_m^k \cdot (n/m)^k$, тоже понятно.

Вопрос:

А как быть в общем случае? Когда остаток от деления произвольный? Понятно, что надо считать число способов отобрать $a$ групп из $m_1$ первых групп, и $b$ групп из m_2 вторых групп, чтобы $a+b=k$. В этом случае это число просто умножать на $n_1^a \cdot n_2^b$. Но как найти все количества таких разбиений?

[iancaple]

Количество разбиений равно коэффициенту при $x^k$ в $(1+n_1 x)^{m_1}(1+n_2 x)^{m_2}$, а то, что $n_2=n_1+1$, $m_1+m_2=m$, $m_1n_1+m_2n_2=n$ не очень-то позволяет это упростить в общем случае.

[deep blue]

Еще вроде так можно посчитать: $\math \sum\limits_{i=0}^{\min(m_2,k)} C_{m_2}^i C_m^{k-i} \left(\dfrac{n-m_2}{m} \right)^{k-i}$

[Zazaqa]

iancaple в сообщении #1074430 писал(а):

Количество разбиений равно коэффициенту при $x^k$ в $(1+n_1 x)^{m_1}(1+n_2 x)^{m_2}$

Как мне нагуглить такие полиномы? По каким ключевым словам?

deep blue в сообщении #1074550 писал(а):

Еще вроде так можно посчитать: $\math \sum\limits_{i=0}^{\min(m_2,k)} C_{m_2}^i C_m^{k-i} \left(\dfrac{n-m_2}{m} \right)^{k-i}$

Спасибо, щас буду проверять.