Комбинаторика. Кол-во разбиений числа на слагаемые.

[C0rWin]

Собственно интересует как подсчитать кол-во разбиений числа на слагаемые(возможны повторения чисел). У меня эта задача свелась к такой, найти кол-во решений уравнения:x_1 + x_2 + ... + x_n = n где все Х не отрицательные числа. Ну и соответственно решение получилось C_n^{2n - 1}. Вопрос верно ли это? И еще как найти рекуррентное соотношение для ответа этой задачи?

Добавлено спустя 1 минуту 55 секунд:

Послал пост и сообразил, что мое решение включайт уйму повторений. Т.е. на вопрос правильно ли это, ответ однозначный не правильно... Тогда вопрос можно ли как то это починить и придти к правильному ответу?

[PAV]

Уточните постановку задачи. Задано ли количество слагаемых? Верно ли, что Вам требуется разбить число $n$ на $n$ слагаемых? И главный вопрос - считаются ли суммы, отличающиеся порядком слагаемых, различными?

[C0rWin]

Суммы отличающиеся порядком слагаемых одинаковы, т.е. это не принципиально. Мне не нужно разбивать число $n$ на $n$ слагаемых, мне нужно получить количество всех возможных комбинаций составить число $n$ из слагаемых. Я просто как пример приведу например для числа 3 получим {3, 2+1, 1+1+1}.

Добавлено спустя 4 минуты 2 секунды:

А ну и просто чтобы пояснить мою первую попытку решения. Я просто подумал, что если x_i=0 то это будет означать что на этом месте на самом деле нет числа. А изначально взял $n$ слагаемых только потому, что это возможный максимум кол-ва слагаемых в сумме (все единицы).

[RIP]

Если я правильно понял, то речь идет о знаменитой функции числа разбиений p(n). Для нее не существует "замкнутого" выражения, известна лишь асимптотика(но очень хорошая, см., например,Литлвуд Дж. — Математическая смесь, стр.91 вверху.)
А еще лучше Эндрюс Г. — Теория разбиений, на стр.83 дана простая асимптотическая формула(5.1.2).

[PAV]

Если порядок слагаемых существенен, то Ваш ответ $C_{2n-1}^n$ правильный. А вот если несущественен, то действительно простой формулы не существует.

[C0rWin]

В том то и дело, что не существенен... А про то что простой закрытой формулы нет я понял когда решил эду задачу с помощью рекурсии и получил ответ вида: p(n) = 1 + \sum\nolimits_{i = 1}^{n - 1} {p(i)}. И судя по всему отсюда уже никак не получить нормальной формулы, можно конечно получить производящую функцию, но не думаю, что это поможет.

Добавлено спустя 11 минут 7 секунд:

Мда... почитал превые страницы книг и понял, что и в этот раз поторопился с ответом.

Добавлено спустя 24 минуты 51 секунду:

Вопрос: возможно ли как то перенести решение этой задачи в теорию графов?

[maxal]

C0rWin писал(а):

Вопрос: возможно ли как то перенести решение этой задачи в теорию графов?

Если у вас эта задача возникла в связи с графами, то может имеет смысл сформулировать исходную задачу?

[C0rWin]

Нет это не связано с графами, я просто пытался как то перенести эту задачу на графы...