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