2014 dxdy logo

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

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




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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
 
 
 
Сообщение30.11.2006, 21:23 
Аватара пользователя
C0rWin писал(а):
Вопрос: возможно ли как то перенести решение этой задачи в теорию графов?

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

 
 
 
 
Сообщение01.12.2006, 03:04 
Нет это не связано с графами, я просто пытался как то перенести эту задачу на графы...

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


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