Рассмотрим наборы из $%k$% натуральных чисел, сумма которых равна заданному числу $%N\ge k$%... Если ли формулы, которые вычисляют сумму из произведений всех таких наборов... то есть $$ \sum_{n_1+\ldots+n_k=N} n_1\cdot\ldots\cdot n_k $$

Понятно, что при двух слагаемых получаем одну сумму, где надо знать только формулу суммы натуральных чисел и сумму квадратов... то есть тут в лоб всё считается ...
При трёх слагаемых получается двойная сумма... и там выражение более громоздкое, и формулы суммы натуральных чисел до четвёртой степени придётся использовать...

Большее я в люб не смотрел... но может это как-то в общем случае не в лоб считается?...

задан 25 Окт 17:56

изменен 25 Окт 17:57

2

вроде такая сумма это коэффициент при $%x^N$% у производящей функции $%(x+2x^2+3x^3+...+Nx^N)^k$%

(25 Окт 18:09) abc

@abc, спасибо... а как-нибудь в конечном виде это находится?

(25 Окт 18:34) all_exist
2

Вроде находится. Получается $%\frac{x^k}{(1-x)^{2k}}$% у которой коэффициент при $%x^N$% равен $%\binom{N+k-1}{2k-1}$%

(25 Окт 19:01) abc
10|600 символов нужно символов осталось
2

Интересно найти чисто комбинаторное решение. Подход с рассмотрением сумм для разных k тоже разумен, так как там вырисовывается общая закономерность ответа. Производящие функции -- тем более эффективный аппарат, но интересно найти прямое доказательство.

Я бы делал так. Берём отрезок длиной N, разделённый на единичные. Там имеется N-1 узел разбиения. Выделим k-1 из них, и назовём "красными". Отрезок будет разбит на k частей с длинами n(1), ... , n(k). Произведению n(1)...n(k) соответствует выбор единичного отрезка в каждой из частей. Назовём выбранные части "синими".

В итоге окажется, что подсчитываемая величина имеет следующий комбинаторный смысл. Имеется слово СКСК...С, где С встречается N раз. Мы выбираем в нём "разреженное подслово" вида ...С...К... ... К...С... , где С встречается k раз. Это довольно естественная самостоятельная комбинаторная задача. Такой выбор определяется чётными длинами пропусков между буквами (включая начальный и конечный). Это 2k целых неотрицательных чисел, сумма которых равна 2N-2k. То есть получается число решений уравнения 2(d(1)+...+d(2k))=2(N-k), а это число сочетаний с повторениями из 2k по N-k, равная C_{N+k-1}^{N-k}, где верхний индекс можно заменить на 2k-1. Ответ совпадает с тем, который указал @abc.

ссылка

отвечен 25 Окт 23:00

Я и забыл какой комбинаторный смысл обычно придается произведению величин. Это же совместный выбор элементов из кучек. Задача получилась не слишком пресной и не слишком громоздкой.

(26 Окт 0:41) abc

@abc, @falcao, спасибо...

(26 Окт 17:03) all_exist
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,005

задан
25 Окт 17:56

показан
63 раза

обновлен
26 Окт 17:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru