Рекурренты в комбинаторике и числа Фибоначчи f(n)
Ошибка.
Попробуйте повторить позже
Сколько имеется 
-значных чисел, у которых все цифры принадлежат множеству 
и любые две соседние цифры
отличаются на 
Подсказка 1
Неочевидно, как сразу выразить интересующее нас количество рекуррентной формулой. Зато, если ввести свою переменную на каждый вариант последней цифры, несложно понять, что происходит при приписывании ещё одной цифры.
Подсказка 2
Полезно посмотреть на начало последовательностей. Это позволяет заметить, как выглядят числа на каждом чётном шаге рекурсии. Осталось только доказать предположение по индукции.
Разобьём числа на пять видов по последней цифре, обозначим их соответствующими символами:
- 1.
-
— количество чисел из 
знаков, которые кончаются на 
- 2.
-
— количество чисел из 
знаков, которые кончаются на 
- 3.
-
— количество чисел из 
знаков, которые кончаются на 
- 4.
-
— количество чисел из 
знаков, которые кончаются на 
- 5.
-
— количество чисел из 
знаков, которые кончаются на 
Тогда напишем рекуррентные соотношения:
 |
Ясно, что 
и 
(например, можно построить биекцию, заменив 
на 
и 
на 
Тогда давайте по индукции
доказывать, что при 
— 
и 
База очевидна, двузначные числа 
Теперь переход с помощью рекурренты:
 |
Теперь у нас спрашивают про 
Получаем
 |
Значит, ответ 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
