2014 dxdy logo

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

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




 
 Задачка по комбинаторике
Сообщение17.11.2015, 12:31 
Сама задача:

$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$. Но как найти все количества таких разбиений?

 
 
 
 Re: Задачка по комбинаторике
Сообщение17.11.2015, 23:22 
Аватара пользователя
Количество разбиений равно коэффициенту при $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$ не очень-то позволяет это упростить в общем случае.

 
 
 
 Re: Задачка по комбинаторике
Сообщение18.11.2015, 12:58 
Еще вроде так можно посчитать: $\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}$

 
 
 
 Re: Задачка по комбинаторике
Сообщение18.11.2015, 15:28 
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}$

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

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


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