Полностью задача звучит так:

Найти число разложений f(n) числа n>1 , имеющих четное число четных слагаемых n =1,...,10. Построить непереборный алгоритм вычисления f(n).

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

задан 17 Мар '13 20:41

изменен 17 Мар '13 20:48

Важное уточнение: различаются ли разложения с одним и тем же набором слагаемых, но разным порядком их расположения? Иными словами, $%13=4+9$% и $%13=9+4$% -- это одно и то же разложение, или два разных? Задача имеет смысл как в той, так и в другой постановке.

(17 Мар '13 20:51) falcao

При такой постановке задачи само число должно быть четным.

(17 Мар '13 20:58) Anatoliy

@Anatoliy: я пропустил условие, что чётным является только число чётных слагаемых, а не всех вместе. Но вообще-то $%n$% не обязано быть чётным: то же число $%13$% можно представить как $%13=9+2+2$% с соблюдением всех условий. Сейчас нужно понять, важен ли порядок слагаемых -- от этого многое зависит.

(17 Мар '13 21:10) falcao

Я имел ввиду разбиение числа только на четные слагаемые. Если иное, то ничего страшного. Ответ убирать не буду. Уже поздно.

(17 Мар '13 21:14) Anatoliy
  1. Нет, наборы не различаются порядком слагаемых. Например:

4 = 2+2

5 = 2+2+1

6 = 2+4 или 2+2+1+1+1

7 = 2+2+1+1+1 или 2+2+3 или 4+2+1

(17 Мар '13 21:29) Archi

@Archi: спасибо за уточнение. Я сейчас готов изложить решение, хотя оно довольно длинное и использует технику производящих функций. Я учитываю также случай, когда нечётное число (не превосходящее $%9$%) представляется в виде суммы одного слагаемого. Чётных слагаемых при этом ноль, то есть такой случай формально подходит. Если он Вам не нужен, то из ответа можно вычесть $%1$% у таких чисел. Скажем, я считаю, что $%f(5)=4$%, так как $%5=3+1+1=1+1+1+1=2+2+1$%, а других возможностей нет. Полезно лишний раз сверить понимание условия.

(18 Мар '13 0:09) falcao

При решении задачи я считаю, что число не разлагается в сумму одного слагаемого. Да, производящие функции - это в тему. Если Вас не затруднит)

(18 Мар '13 4:20) Archi
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
3

Я здесь провёл полное исследование задачи и написал довольно длинный текст. Сразу хочу предупредить, что если имелось в виду всего лишь составление программы для нахождения значений $%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$%.

ссылка

отвечен 18 Мар '13 5:28

изменен 18 Мар '13 7:16

Спасибо Вам!

(18 Мар '13 11:29) Archi
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,497
×1,314
×58

задан
17 Мар '13 20:41

показан
4874 раза

обновлен
18 Мар '13 11:29

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

по почте:

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

по RSS:

Ответы

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

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