Сколько существует различных неотриц. целых решени

Сообщение №1468 от Alex W. 24 октября 2001 г. 12:36
Тема: Сколько существует различных неотриц. целых решени

Известен ли ответ на следующий вопрос:
Сколько существует различных неотриц. целых решений следующего ур-я :
X1 + X2 + X3 + X4 + ... + Xk = N
где N >= k

Хотя бы оценочное значение


Отклики на это сообщение:

> Известен ли ответ на следующий вопрос:
> Сколько существует различных неотриц. целых решений следующего ур-я :
> X1 + X2 + X3 + X4 + ... + Xk = N
> где N >= k

> Хотя бы оценочное значение

Что-то вроде С^k_{N+k} (число сочетаний)


> > Известен ли ответ на следующий вопрос:
> > Сколько существует различных неотриц. целых решений следующего ур-я :
> > X1 + X2 + X3 + X4 + ... + Xk = N
> > где N >= k

> > Хотя бы оценочное значение

> Что-то вроде С^k_{N+k} (число сочетаний)

Неверно. Классическая задача, решенная Харди и Рамануджаном.
Подробности: Эндрюс "Теория разбиений"
Чандрасекхаран &Co "Арифметические функции",
годится и любая популярная брошюра про Рамануджана.
В случае дальнейших проблем -
mailto; vche@smr.ru


> Известен ли ответ на следующий вопрос:
> Сколько существует различных неотриц. целых решений следующего ур-я :
> X1 + X2 + X3 + X4 + ... + Xk = N
> где N >= k

> Хотя бы оценочное значение

Точная формула (Харди - Раманужан) слишком громоздка, чтоб ее здесь приводить. Найдите книгу, которую посоветовал Михалыч: Дж.Эндрюс "Теория разбиений" (М., Наука, 1982). Книга очень хорошая.

Если нужен порядок роста функции, то это

exp(sqrt(N)) / N

Это не ассимптотический эквивалент, там есть еще константы, могу найти, если нужно


> > Известен ли ответ на следующий вопрос:
> > Сколько существует различных неотриц. целых решений следующего ур-я :
> > X1 + X2 + X3 + X4 + ... + Xk = N
> > где N >= k

> > Хотя бы оценочное значение

> Точная формула (Харди - Раманужан) слишком громоздка, чтоб ее здесь приводить. Найдите книгу, которую посоветовал Михалыч: Дж.Эндрюс "Теория разбиений" (М., Наука, 1982). Книга очень хорошая.

> Если нужен порядок роста функции, то это

> exp(sqrt(N)) / N

> Это не ассимптотический эквивалент, там есть еще константы, могу найти, если нужно

Правильнее записать так:

exp(sqrt(N) - ln(N))


> Известен ли ответ на следующий вопрос:
> Сколько существует различных неотриц. целых решений следующего ур-я :
> X1 + X2 + X3 + X4 + ... + Xk = N
> где N >= k

> Хотя бы оценочное значение

Столько, сколько способов разместить k-1 перегородок между N одинаковыми предметами.
k-1
То есть C
N+k-1
(число сочетаний, как и написал Volody)


> > Известен ли ответ на следующий вопрос:
> > Сколько существует различных неотриц. целых решений следующего ур-я :
> > X1 + X2 + X3 + X4 + ... + Xk = N
> > где N >= k

> > Хотя бы оценочное значение

Столько, сколько способов разместить k-1 перегородок между N одинаковыми предметами.
То есть C^(k-1)_(N+k-1)
(число сочетаний, как и написал Volody)


На сформулированную задачу ответ действительно - сочетания.

Разбиение - это неубывающая последовательность натуральных чисел, сумма которых N.

> > > Известен ли ответ на следующий вопрос:
> > > Сколько существует различных неотриц. целых решений следующего ур-я :
> > > X1 + X2 + X3 + X4 + ... + Xk = N
> > > где N >= k

> > > Хотя бы оценочное значение

> Столько, сколько способов разместить k-1 перегородок между N одинаковыми предметами.
> То есть C^(k-1)_(N+k-1)
> (число сочетаний, как и написал Volody)


А также гласных?

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

> На сформулированную задачу ответ действительно - сочетания.

> Разбиение - это неубывающая последовательность натуральных чисел, сумма которых N.


> > > > Известен ли ответ на следующий вопрос:
> > > > Сколько существует различных неотриц. целых решений следующего ур-я :
> > > > X1 + X2 + X3 + X4 + ... + Xk = N
> > > > где N >= k

> > > > Хотя бы оценочное значение

> > Столько, сколько способов разместить k-1 перегородок между N одинаковыми предметами.
> > То есть C^(k-1)_(N+k-1)
> > (число сочетаний, как и написал Volody)


> > > Известен ли ответ на следующий вопрос:
> > > Сколько существует различных неотриц. целых решений следующего ур-я :
> > > X1 + X2 + X3 + X4 + ... + Xk = N
> > > где N >= k

> > > Хотя бы оценочное значение

> > Что-то вроде С^k_{N+k} (число сочетаний)

> Неверно. Классическая задача, решенная Харди и Рамануджаном.
> Подробности: Эндрюс "Теория разбиений"
> Чандрасекхаран &Co "Арифметические функции",
> годится и любая популярная брошюра про Рамануджана.
> В случае дальнейших проблем -
> mailto; vche@smr.ru

Приношу извинения за неполноту предыдущего ответа.
Формулировка задачи действительно неоднозначна и может быть интерпретирована ЧЕТЫРЕХ
различных версиях.

1.Разбиения упорядочены (т.е 2+2+1=5 и 2+1+2=5 - различные разбиения)

1.1 Параметр _к_ фиксирован
ОТВЕТ "С "из(n-1) по (k-1)"" - число способов,которыми можно разместить к-1 черточек в (n-1) промежутке.
1.2 Параметр _к_ НЕ фиксирован
ОТВЕТ 2^(n-1) - из тех же соображений (черточка либо стоит, либо нет).

2. Разбиения неупорядоченные (т.е. вышеприведенныеи представления числа 5 различны.

2.1. Параметр _к_ фиксирован
ОТВЕТ Полином степени (к-1), старший член которого равен
(n^(k-1))/(k-1)!k!
2.2 Параметр _к_ НЕ фиксирован (задача Харди-Рамануджана)
ОТВЕТ (см. пост 1475 от Б.Б.)
Подробности и методы - см. также
М.Холл "Комбинаторика" М.:Мир, 1970


> А также гласных?

> Для начала неплохо бы заметить, что автор вопроса неточно его сформулировал: ответ будет зависеть от того, какие решения считаются различными.
Неплохое замечание.
Но у меня еще одно. Требуется решить не в натуральных числах, а в неотрицателных целых. Т.е. несколько иксов могут быть нулевыми. А следовательно, нужно учесть возможность не ( л-1) перегородок, а и (k-2),(k-3) и т.д.


> > А также гласных?

> > Для начала неплохо бы заметить, что автор вопроса неточно его сформулировал: ответ будет зависеть от того, какие решения считаются различными.
> Неплохое замечание.
> Но у меня еще одно. Требуется решить не в натуральных числах, а в неотрицателных целых. Т.е. несколько иксов могут быть нулевыми. А следовательно, нужно учесть возможность не ( л-1) перегородок, а и (k-2),(k-3) и т.д.

Оч.хор.! Не заметил.
Но думается, что автор имел в виду что-то очень простое, мы теоретизируем.
Неплохо бы было и автору высказаться... А он молчит...


> > > > Известен ли ответ на следующий вопрос:
> > > > Сколько существует различных неотриц. целых решений следующего ур-я :
> > > > X1 + X2 + X3 + X4 + ... + Xk = N
> > > > где N >= k

> > > > Хотя бы оценочное значение

> > > Что-то вроде С^k_{N+k} (число сочетаний)

> > Неверно. Классическая задача, решенная Харди и Рамануджаном.
> > Подробности: Эндрюс "Теория разбиений"
> > Чандрасекхаран &Co "Арифметические функции",
> > годится и любая популярная брошюра про Рамануджана.
> > В случае дальнейших проблем -
> > mailto; vche@smr.ru

> Приношу извинения за неполноту предыдущего ответа.
> Формулировка задачи действительно неоднозначна и может быть интерпретирована ЧЕТЫРЕХ
> различных версиях.

> 1.Разбиения упорядочены (т.е 2+2+1=5 и 2+1+2=5 - различные разбиения)

> 1.1 Параметр _к_ фиксирован
> ОТВЕТ "С "из(n-1) по (k-1)"" - число способов,которыми можно разместить к-1 черточек в (n-1) промежутке.
> 1.2 Параметр _к_ НЕ фиксирован
> ОТВЕТ 2^(n-1) - из тех же соображений (черточка либо стоит, либо нет).

> 2. Разбиения неупорядоченные (т.е. вышеприведенныеи представления числа 5 различны.

> 2.1. Параметр _к_ фиксирован
> ОТВЕТ Полином степени (к-1), старший член которого равен
> (n^(k-1))/(k-1)!k!
> 2.2 Параметр _к_ НЕ фиксирован (задача Харди-Рамануджана)
> ОТВЕТ (см. пост 1475 от Б.Б.)
> Подробности и методы - см. также
> М.Холл "Комбинаторика" М.:Мир, 1970

У меня возник вопрос, вы "Xk=0" включали(в вопросе было "неотрицательных")? Поскольку для N=2 И k=2
ответ вроде 3, а не С^1_1=1.


После прочтения верхних постов вопрос снят



Имеет ли эта задача содержательные практические приложения.
(Не считая перегородок.)
Меня впечатлило, что Volody привел решение по памяти.



Решением уравнения называется упорядоченный набор....
Так что
> > На сформулированную задачу ответ действительно - сочетания.

Единственно что не было оговорено - k - переменная или константа.

Что имел в виду автор - можно только догадываться.

> А также гласных?

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

> > На сформулированную задачу ответ действительно - сочетания.

> > Разбиение - это неубывающая последовательность натуральных чисел, сумма которых N.

>
> > > > > Известен ли ответ на следующий вопрос:
> > > > > Сколько существует различных неотриц. целых решений следующего ур-я :
> > > > > X1 + X2 + X3 + X4 + ... + Xk = N
> > > > > где N >= k

> > > > > Хотя бы оценочное значение

> > > Столько, сколько способов разместить k-1 перегородок между N одинаковыми предметами.
> > > То есть C^(k-1)_(N+k-1)
> > > (число сочетаний, как и написал Volody)


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100