2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Количество разбиений натурального числа на слагаемые
Сообщение24.02.2010, 15:54 
Здравствуйте, не могу понять как решить следующую задачу.
Найти количество разбиений натурального числа $n$ на $k$ неотрицательных натуральных слагаемых, не превосходящих $z$. Разбиения, отличающиеся порядком слагаемых считаются разными.
Если бы не было верхнего ограничения на величину слагаемого, то решение найти не трудно.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение24.02.2010, 16:04 
Аватара пользователя
$$
N(n,k,z) = \sum_{i=0}^z N(n-i,k-1,z); \,\,\, N(n,1,z) = \text{понятно чему}
$$
Похоже на числа Стирлинга второго рода. Наверняка что-нибудь известное.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение24.02.2010, 20:18 
Это будет рекурсивная формула.
Можно использовать также и принцип включения-исключения.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 06:43 
Аватара пользователя
Вычислите коэффициент при $x^n$ в
$$(1+x+x^2+\dots+x^z)^k = (1-x^{z+1})^k (1-x)^{-k}$$

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 13:12 
maxal
А если считать разбиения одинаковыми, при условии, что они совпадают с точностью до перестановки - есть ли формула для их кол-ва?
(5,2,2)=(2,5,2)=(2,2,5)
(6,2,1)=(6,1,2)=(2,1,6)=(2,6,1)=(1,6,2)=(1,2,6)

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 13:17 
Аватара пользователя
Тогда ещё хуже.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 13:54 
Аватара пользователя
Реккурентная формула для вычисления $N(n,k,z)$ требует порядка $k \cdot n \cdot z$ операций. Не уверен, что "красивая формула" (если она, конечно, существует) даст существенно лучший результат.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 15:55 
Аватара пользователя
Профессор Снэйп
Даст. Этот подход post292008.html#p292008 дает формулу в виде суммы из ~ n/(z+1) слагаемых.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 17:40 
Аватара пользователя
maxal в сообщении #292122 писал(а):
Профессор Снэйп
Даст. Этот подход post292008.html#p292008 дает формулу в виде суммы из ~ n/(z+1) слагаемых.

Я не совсем понимаю, как там делить на $(1+x)^k$.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 18:23 
Аватара пользователя
Профессор Снэйп
$$\sum_{j=0}^{\lfloor n/(z+1)\rfloor} (-1)^{n+zj} \binom{k}{j} \binom{-k}{n-(z+1)j}$$

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 19:03 
Аватара пользователя
Я не совсем понял, откуда взялась формула, но даже не это важно. Слагаемые --- биномиальные коэффициенты, а их вычисление тоже требует времени, так что выигрыш в объёме вычислений от этой формулы не очевиден.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 21:30 
Аватара пользователя
Профессор Снэйп в сообщении #292203 писал(а):
Я не совсем понял, откуда взялась формула, но даже не это важно. Слагаемые --- биномиальные коэффициенты, а их вычисление тоже требует времени, так что выигрыш в объёме вычислений от этой формулы не очевиден.

Формула взялась отсюда: post292008.html#p292008
А биномиальные коэффициенты - сущности существующие вне контекста задачи. Можно считать, например, что все они заранее вычислены (до некоторой границы), и задачи с различными параметрами (до той же границы) решаются конвеерно.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение25.02.2010, 23:34 
maxal в сообщении #292008 писал(а):
Вычислите коэффициент при $x^n$ в
$$(1+x+x^2+\dots+x^z)^k = (1-x^{z+1})^k (1-x)^{-k}$$


maxal,
расскажите пожалуйста или дайте намёк почему решением задачи является указанный вами коэффцициент?И как вы получили формулу для коэффициента?

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение26.02.2010, 01:20 
Аватара пользователя
dronbas в сообщении #292371 писал(а):
расскажите пожалуйста или дайте намёк почему решением задачи является указанный вами коэффцициент?

Каждой композиции $n=m_1 + m_2 + \dots + m_k$ соответствует произведение $x^{m_1} x^{m_2} \dots x_{m_k}$ в разложении
$$(1+x+x^2+\dots+x^z)(1+x+x^2+\dots+x^z)\dots (1+x+x^2+\dots+x^z)=(1+x+x^2+\dots+x^z)^k$$
где $x^{m_1}$ берется из первой скобки, $x^{m_2}$ - из второй и т.д.
dronbas в сообщении #292371 писал(а):
И как вы получили формулу для коэффициента?

Представляете каждый множитель в произведении $(1-x^{z+1})^k (1-x)^{-k}$ в виде ряда:
$$\sum_{i=0}^\infty (-1)^i \binom{k}{i} x^{i(z+1)} \sum_{j=0}^\infty (-1)^j \binom{-k}{j} x^j = \sum_{i=0}^\infty \sum_{j=0}^\infty (-1)^{i+j} \binom{k}{i} \binom{-k}{j} x^{i(z+1)+j}$$
Нас интересует коэффициент при $x^n$, для которого $i(z+1)+j=n,$ то есть, $j=n- i(z+1)$.

 
 
 
 Re: Количество разбиений натурального числа на слагаемые
Сообщение26.02.2010, 12:24 
А как посчитать варианты разбиений $N= m_1+m_2+...+m_k$ ровно на $k$ слагаемых $m_i > 0$. Понятно что это отличается от случая не более, чем $k$ слагаемых.


Вопрос остался без ответа. Варианты разбиений $N= m_1+m_2+...+m_k$ на не более чем $k$ слагаемых с условием $ 0 \leq m_1 \leq m_2\leq ...\leq m_k \leq z$ можно как то по простому пересчитать?

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


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