2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Комбинаторика. Кол-во разбиений числа на слагаемые.
Сообщение14.10.2006, 17:57 


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

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

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

 Профиль  
                  
 
 
Сообщение14.10.2006, 18:51 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение15.10.2006, 01:45 


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

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

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

 Профиль  
                  
 
 
Сообщение15.10.2006, 03:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение15.10.2006, 08:43 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение15.10.2006, 14:30 


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

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

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

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

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

 Профиль  
                  
 
 
Сообщение30.11.2006, 21:23 
Модератор
Аватара пользователя


11/01/06
5660
C0rWin писал(а):
Вопрос: возможно ли как то перенести решение этой задачи в теорию графов?

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

 Профиль  
                  
 
 
Сообщение01.12.2006, 03:04 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group