Количество разбиений натурального числа на слагаемые

[maxal]

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$ можно как то по простому пересчитать?

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

[Профессор Снэйп]

maxal в сообщении #292302 писал(а):

А биномиальные коэффициенты - сущности существующие вне контекста задачи. Можно считать, например, что все они заранее вычислены...

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

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

[maxal]

Профессор Снэйп в сообщении #292592 писал(а):

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

Обсуждали тут: topic14523.html

Профессор Снэйп в сообщении #292592 писал(а):

При натуральных $x$ и $y$ лучше всего, вероятно, через треугольник Паскаля. А при произвольных $x$, в частности, при целых отрицательных... даже не знаю.

При целых отрицательных - то же самое, они же сводятся к "обычным":

$$\binom{-k}{m} = (-1)^m \binom{k+m-1}{m}$$