дискретная-математика - Разбиения числа n>1, имеющие четное число четных слагаемых при n=1,...,10

Я здесь провёл полное исследование задачи и написал довольно длинный текст. Сразу хочу предупредить, что если имелось в виду всего лишь составление программы для нахождения значений $%f(n)$%, то это делается совсем просто. Такая программа для Maple (с рекурсивным вызовом) занимает около десяти строк, и считает сравнительно быстро на не очень больших числах. Однако для больших значений $%n$% такая процедура уже не очень эффективна, да и сама по себе эта программа не слишком интересна. Скажем, для вычисления значения $%f(100)=3146214$% программа работала минуты две. Поэтому я предлагаю Вашему вниманию дальнейший текст. Буду готов ответить на любые вопросы по его содержанию.

Для удобства полагаем $%f(0)=1$% (ноль представим одним способом в виде "пустой суммы"); $%f(1)=1$%. Случай, когда слагаемое в сумме одно, и оно равно $%n$% мы тоже будем учитывать (для нечётных $%n$% от $%1$% до $%9$%).

Наша основная цель -- найти производящую функцию последовательности $%f(n)$%, которой называется сумма степенного ряда $$F(t)=f(0)+f(1)t+f(2)t^2+\cdots+f(n)t^n+\cdots,$$ с которым пока можно оперировать чисто формально, не думая о его сходимости. Ответ будет дан в виде рациональной функции, то есть частного двух многочленов. При этом будет понятно, что ряд сходится при всех $%|t| < 1$%.

Прежде всего, пусть число $%n$% каким-то способом представлено в виде суммы одного или нескольких слагаемых, принимающих натуральные значения от $%1$% до $%10$%. Порядок слагаемых в сумме не важен. Количество чётных слагаемых, согласно условию, полагаем чётным (в частности, оно может быть равно нулю).

Обозначим через $%2k$% сумму всех чётных слагаемых, входящих в данное представление. Ясно, что $%0\le k\le\lfloor{n/2}\rfloor$%. Положим также $%m=n-2k$% -- это сумма нечётных слагаемых. Нам достаточно знать, сколькими способами произвольное число $%m$% представляется в виде суммы слагаемых, принимающих значения $%1,3,5,7,9$%, а также сколькими способами число $%2k$% представимо в виде суммы чётного числа чётных слагаемых. Последнее равносильно вопросу о том, сколькими способами число $%k$% представляется в виде суммы чисел от $%1$% до $%5$%, чтобы количество слагаемых было чётным.

Введём такие обозначения: пусть $%g(n)$% есть количество представлений $%n\ge0$% в виде суммы одного или нескольких нечётных чисел от $%1$% до $%9$%. Также пусть $%h(n)$% есть количество способов представить число $%n\ge0$% в виде суммы чисел от $%1$% до $%5$%, где число слагаемых обязано быть чётным. Тогда нужное нам значение $%f(n)$% выражается следующей формулой: $$f(n)=\sum\limits_{k=0}^{\lfloor{n/2}\rfloor}g(n-2k)h(k).$$ Таким образом, задача сводится к вычислению функций $%g$% и $%h$%.

Первая из задач достаточно стандартна. Пусть мы представили $%n$% в виде суммы нечётных чисел от $%1$% до $%5$%, и пусть $%x_i$% есть количество слагаемых, равных $%i$%. Тогда $%x_1+3x_3+5x_5+7x_7+9x_9=n$%, где все $%x_i$% -- целые неотрицательные.

Рассмотрим такое произведение пяти бесконечных степенных рядов: $$(1+t+t^2+\cdots)(1+t^3+t^6+\cdots)(1+t^5+t^{10}+\cdots)(1+t^7+t^{14}+\cdots)(1+t^9+t^{18}+\cdots).$$ Если эти ряды формально перемножить между собой (как многочлены, начиная с младших членов), то получится степенной ряд, у которого коэффициент при $%t^n$% будет равен как раз $%g(n)$%. В самом деле, из первой скобки мы берём какое-то $%t^{x_1}$%, из второй -- какое-то $%t^{3x_3}$% и так далее, и при перемножении получится $%t$% в степени $%x_1+3x_3+5x_5+7x_7+9x_9$%, и коэффициент при $%t^n$% будет в точности такой, сколькими способами $%n$% можно представить в этом виде. Таким образом, производящая функция $%G(t)$% последовательности $%g(n)$% будет равна $$G(t)=\frac1{(1-t)(1-t^3)(1-t^5)(1-t^7)(1-t^9)}.$$ Здесь мы воспользовались формулой для суммы членов бесконечной геометрической прогрессии, что имеет смысл при $%|t| < 1$%.

Имея такую формулу, мы фактически получаем способ рекуррентного вычисления коэффициентов ряда при помощи деления многочленов "столбиком" (начиная с младших членов).

Теперь обратимся к функции $%h(n)$%. Чтобы её найти, придётся ввести несколько обозначений. Прежде всего, для каждого $%r$% от $%1$% до $%5$% рассмотрим две величины: $%e_r(n)$% и $%h_r(n)$%. Они обозначают количество представлений числа $%n\ge0$% в виде суммы слагаемых, принимающих натуральные значения от $%1$% до $%r$%, причём в первом случае (для $%e_r(n)$%) это количество может быть любым, а во втором случае (для $%h_r(n)$%) оно должно быть чётным. Нас будет интересовать величина $%h(n)=h_5(n)$%. Заглавными буквами мы будем обозначать соответствующие производящие функции последовательностей. Заметим, что для производящей функции $%E_r(t)$% уже имеется готовая формула: $$E_r(t)=\frac1{(1-t)(1-t^2)\ldots(1-t^r)},$$ которая получается тем же способом, что и выше. А производящие функции $%H_r(t)$% мы найдём по рекуррентной формуле, которую сейчас выведем.

Очевидно, что $%H_1(t)=1+t^2+t^4+t^6+\cdots=1/(1-t^2)$%, как числа здесь представляются в виде суммы единиц, и число способов такого представления равно нулю для нечётных $%n$% и единице для чётных $%n$%. Пусть теперь $%r > 1$%, и все функции для меньших значений уже найдены. Заметим, что $%e_r(n)-h_r(n)$% есть количество представлений $%n$% в виде суммы слагаемых с теми же условиями, что и для $%e_r(n)$%, только теперь уже количество слагаемых нечётно.

Пусть мы представили $%n$% в виде суммы каких-то слагаемых от $%1$% до $%r$%, где слагаемое $%i$% встретилось $%y_i$% раз. Имеет место равенство $%y_1+2y_2+\cdots+ry_r=n$%, где сумма $%y_1+y_2+\cdots+y_r$% нечётна (это количество слагаемых). Мы хотим найти число таких представлений, вычитая его далее их $%e_r(n)$% и получая $%h_r(n)$%. Возможно два случая: $%y_r$% может быть равно или не равно нулю. Допустим первое. Тогда слагаемое $%y_r$% отовсюду исчезает, и мы получаем количество представлений с нечётным числом слагаемых для предыдущего значения, то есть $%e_{r-1}(n)-h_{r-1}(n)$%. Запомним это, и рассмотрим случай, когда слагаемое $%y_r$% нечётно. Здесь мы имеем $%y_r\ge1$%, поэтому можно вычесть $%1$% из $%y_r$% и получить на одно слагаемое меньше, с суммой $%n-r$%. Число слагаемых теперь чётно, и их количество равно $%h_r(n-r)$%.

Нами получена следующая рекуррентная формула: $%h_r(n)=e_r(n)-(e_{r-1}(n)-h_{r-1}(n))-h(n-r)$%. Из неё легко получить рекуррентное соотношение для производящих функций. Делается это следующим стандартным способом: предыдущее равенство домножается на $%t^n$% и суммируется по всем $%n\ge0$%. При этом все строчные буквы фактически заменяются на заглавные, и только в последнем слагаемом надо учесть, что $%h(m)$% при любом $%m$% будет домножаться на степень $%t$%, показатель которой на $%r$% больше числа $%m$%, то есть произойдёт умножение на $%t^r$%. Получится следующее:

$$H_r(t)=E_r(t)-(E_{r-1}(t)-H_{r-1}(t))-t^rH_r(t).$$ Здесь пока что $%H_r(t)$% содержится в обеих частях, но после арифметического преобразования мы будем иметь $$H_r(t)=\frac{E_r(t)-E_{r-1}(t)+H_{r-1}(t)}{1+t^r}.$$ По этой формуле мы можем последовательно вычислить все $%H_r$%, и для $%r=5$% получается следующая функция (я считал в Maple): $$H_5(t)=\frac{1-2t+2t^2-t^3+2t^4-2t^5+2t^6-t^7+t^8-t^9+t^{10}}{(1-t)^2(1-t^2)(1-t^3)(1-t^5)(1+t^2)(1+t^3)(1+t^4)(1+t^5)}.$$ Теперь осталось сделать завершающий шаг. Обратим внимание на формулу, выражающую $%f$% через $%g$% и $%h$%. Она может быть переписана в таком виде: $$f(n)=\sum\limits_{m+2k=n}g(m)h(k),$$ где суммирование ведётся по всем парам целых неотрицательных чисел с указанным условием. Переведём это равенство на язык производящих функций. Как и выше, домножим всё на $%t^n$% и просуммируем, получая $$F(t)=\sum\limits_{n\ge0}\sum\limits_{m+2k=n}g(m)t^m\cdot h(k)t^{2k}=\sum\limits_{m\ge0}g(m)t^m\cdot\sum\limits_{k\ge0}h(k)t^{2k}=G(t)H(t^2).$$ Таким образом, искомая производящая функция окончательно найдена. При желании, я могу указать её явный вид. Она представляет собой частное многочлена $%20$%-й степени с небольшими коэффициентами и многочлена $%77$%-й степени. Эта функция содержит всю информацию о последовательности $%f(n)$% -- подобно тому, как функция $%1/(1-t-t^2)$% содержит всю информацию о последовательности чисел Фибоначчи. Здесь также имеется рекуррентная формула, но она весьма длинная. Фактически, там каждый член выражается через $%77$% предыдущих. Коэффициенты, правда, тоже небольшие (их можно увидеть, если раскрыть все скобки в знаменателе).

Но здесь нет необходимости всё это делать, так как выше уже было сказано, что когда мы "столбиком" делим многочлен на многочлен, то это и есть алгоритм получения требуемых значений $%f(n)$%.

Вот, на всякий случай, начальные значения для $%f(n)$%, начиная с нулевого: $$1,1,1,2,3,4,6,8,12,16,22,28,39,50,65,84,108,136,172,214,268,\ldots.$$ В частности, $%f(20)=268$%.