2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение26.02.2010, 15:36 
Аватара пользователя
Yu_K в сообщении #292494 писал(а):
А как посчитать варианты разбиений $N= m_1+m_2+...+m_k$ ровно на $k$ слагаемых $m_i > 0$. Понятно что это отличается от случая не более, чем $k$ слагаемых.

Сведите к композиции $N-k= (m_1-1)+(m_2-1)+\dots+(m_k-1)$.
Yu_K в сообщении #292494 писал(а):
Вопрос остался без ответа. Варианты разбиений $N= m_1+m_2+...+m_k$ на не более чем $k$ слагаемых с условием $ 0 \leq m_1 \leq m_2\leq ...\leq m_k \leq z$ можно как то по простому пересчитать?

Вам ответили выше. По-простому - никак, только через рекуррентную формулу. Разбиения в смысле подсчёта гораздо хуже композиций.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение26.02.2010, 15:51 
Аватара пользователя
maxal в сообщении #292302 писал(а):
А биномиальные коэффициенты - сущности существующие вне контекста задачи. Можно считать, например, что все они заранее вычислены...

Ну, если так, то готов признать Вашу правоту.

Кстати, а какова временная сложность вычисления биномиальных коэффициентов. То есть сколько умножений/сложений нужно сделать по оптимальному алгоритму для вычисления $\binom{x}{y}$? И каков этот оптимальный алгоритм? При натуральных $x$ и $y$ лучше всего, вероятно, через треугольник Паскаля. А при произвольных $x$, в частности, при целых отрицательных... даже не знаю.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение26.02.2010, 16:18 
Аватара пользователя
Профессор Снэйп в сообщении #292592 писал(а):
Кстати, а какова временная сложность вычисления биномиальных коэффициентов. То есть сколько умножений/сложений нужно сделать по оптимальному алгоритму для вычисления $\binom{x}{y}$? И каков этот оптимальный алгоритм?

Обсуждали тут: topic14523.html
Профессор Снэйп в сообщении #292592 писал(а):
При натуральных $x$ и $y$ лучше всего, вероятно, через треугольник Паскаля. А при произвольных $x$, в частности, при целых отрицательных... даже не знаю.

При целых отрицательных - то же самое, они же сводятся к "обычным":
$$\binom{-k}{m} = (-1)^m \binom{k+m-1}{m}$$

 
 
 [ Сообщений: 18 ]  На страницу Пред.  1, 2


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