Есть лестница высоты N, каждый раз можно совершать прыжок не более чем на K ступенек. Сколько есть способов забраться на вершину? Как эта задача решается в общем случае? Для K=2 все довольно очевидно, для K=4 получается такое соотношение: $$x(n) = x(n-1) +x(n-2) + x(n-3) +x(n-4), x(1) = 1, x(2) = 2, x(3) = 4, x(4) = 8$$

Потом можно записать производящую функцию

$$1+2z+4z^2+8z^3+\sum^{\infty}_{n=4}a_nz^n $$ После преобразований получится

$$G(z) = \frac{1-5z+z^2+7z^3}{ 1-z-z^2-z^3-z^4}$$

Но у уравнения $$1-z^2-z^3-z^4=0$$ получается 2 иррациональных и 2 комплексных корня, и дальше не очень понятно что делать

задан 30 Мар '19 21:16

изменен 30 Мар '19 21:37

@leonardeuler: там в уравнении пропущено z. Правда, это ничего не меняет -- корни всё равно "плохие", и найти их можно разве что приближённо. Кроме как найти производящую функцию, здесь мало что можно предложить. Правда, у Вас она найдена неверно: в числителе должна быть единица.

См. здесь, а также здесь.

(30 Мар '19 22:04) falcao

@falcao А где у меня ошибка в вычислении производящей функции? https://ibb.co/4PDcHzp

(30 Мар '19 22:41) leonardeuler

@leonardeuler: ошибок там много. При переходе от первой строчки ко второй пропущены множители z, z^2, ... перед суммами. Правда, потом они снова появляются. В конце -- неверные равенства с участием G-a0-a1-a2-a3 и т.п. -- там ведь a1z, a2z^2, ... должно быть.

Вообще, это плохой способ чисто технически: надо брать рекуррентное равенство a(n+4)=a(n+3)+...+a(n), домножать на z^{n+4}, выносить степени, и суммировать по n>=0. Так всё намного "прозрачнее", и проще искать ошибки в случае чего.

(30 Мар '19 23:05) falcao

@falcao А что делать потом? Нашел корни полинома z1,z2,z3,z4, разложил на сумму простых дробей вида A/(z-z1) + B/(z-z2)... Для n-го члена получилась формула (-A/z1)z1^(-n) + (-B/z2)z2^(-n) + .. Это верно?

(31 Мар '19 15:43) leonardeuler

@leonardeuler: я не уверен, что такую формулу вообще надо получать. Всё равно этих корней мы в явном виде не знаем. В принципе, после разложения на простейшие дроби всё это получается, но такая работа представляется лишней.

(31 Мар '19 16:22) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,870
×1,509
×1,127

задан
30 Мар '19 21:16

показан
321 раз

обновлен
31 Мар '19 16:22

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

по почте:

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

по RSS:

Ответы

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

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