2014 dxdy logo

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

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




 
 Количество различных натуральных слагаемых для заданной сумм
Сообщение18.01.2013, 19:40 
Дана некоторая натуральная сумма S из трех натуральных слагаемых A, B и C (слогаемые выбираются без учета порядка). Сколькими способами можно задать данную сумму? Решается ли эта задача аналитически? К примеру, если $S = 3$, то задать сумму можно единственным способом $A = 1, B = 1, C = 1$, если сумма $S = 6$, то задать ее можно двумя различными способами $A = 1, B = 1, C = 4$ и $A = 1, B = 2, C = 3$.

 
 
 
 Re: Количество различных натуральных слагаемых для заданной сумм
Сообщение18.01.2013, 19:43 
goganchic в сообщении #673348 писал(а):
если сумма $S = 6$, то задать ее можно двумя различными способами $A = 1, B = 1, C = 4$ и $A = 1, B = 2, C = 3$.
У Вас слагаемые упорядоченные? (т.е. порядок слагаемых неважен?). Об этом желательно явно писать.
Вообще, задача, конечно, решается. Что из себя представляет геометрически множество целых точек $(x,y,z)$ таких, что $x\leqslant y\leqslant z, \ x,y,z\geqslant 1$ и $x+y+z=S$?
Попробуйте сначала решить задачу для одной и для двух переменных. Каков общий вид решения, представьте себе примерно.
Можно, также, поскольку число слагаемых мало, свести случай упорядоченных слагаемых к случаю произвольных целых слагаемых, исключая разные варианты с $x=y$ или $x=y=z$ и т.п.
Вот уже 2 способа решения задачи :-)

 
 
 
 Re: Количество различных натуральных слагаемых для заданной сумм
Сообщение18.01.2013, 21:18 
Sonic86, спасибо большое за совет, но не могли бы вы несколько подробнее объяснить куда копать?

 
 
 
 Re: Количество различных натуральных слагаемых для заданной сумм
Сообщение19.01.2013, 18:37 
Разбиение чисел - это классика.
Задача поставлена и довольно глубоко исследована еще Эйлером.
В общем случае, она довольно сложна.
Но, если слагаемых именно три - все довольно просто.
Но придется рассмотреть 6 случаев (в зависимости от остатков от деления числа $S$ на 2 и 3).

 
 
 
 Re: Количество различных натуральных слагаемых для заданной сумм
Сообщение19.01.2013, 18:58 
Аватара пользователя
Задача о количестве представлений $S$ суммой трех неотрицательных целых чисел рассмотрена, например, в книге К. Чандрасекхарана "Арифметические функции", решается через производящие функции, ответ -- ближайшее к $(S+3)^2/12$ целое число.

Разбиений $S$ на натуральные числа столько же, сколько разбиений $S-3$ на неотрицательные целые. Так что в Вашей задаче ответ -- ближайшее к $S^2/12$ целое число. Для $S=6$ Вы почему-то выпустили $6=2+2+2$.

 
 
 
 Re: Количество различных натуральных слагаемых для заданной сумм
Сообщение19.01.2013, 19:00 
goganchic, Вы попытались что-нибудь сделать из предложенного? Попытайтесь, дальше можно будет подсказывать, а то так непонятно, что Вам непонятно.
Конкретно для трех слагаемых просто:
0. Погуглите книжки по комбинаторике и почитайте.
1. Решите сначала задачу для одного и двух слагаемых. Посмотрите, что получилось. Предположите общую формулу. Попробуйте вывести ее для трех слагаемых методом неопределенных коэффициентов.
2. Попробуйте найти число $N(x,y,z: x+y+z=S, x,y,z\in\mathbb{N})$ всех натуральных чисел $x,y,z$ таких, что $x+y+z=S$. Как эта функция связана с Вашей функцией, чем отличается, ключевое слово - перестановки. Как можно точно посчитать число разбиений на три слагаемых?
3. Есть же еще метод производящих функций (я вечно про него забываю). Пусть искомая последовательность $a_n$. Из ее определения попробуйте посчитать $f(x)=\sum\limits_{n=0}^{\infty}a_nx^n$, а дальше $n$-й член можно найти с помощью дифференцирования $f(x)$ и подстановки $x=0$.

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


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