способ вычисления N-го Фибоначчи с факториалом

Question

Во время моих попыток решить leetcode 70, поднимаясь по лестнице, я подумал об ответе, в котором используются факториалы (сколько разных способов образовать линию с одинаковыми элементами).Позже я подумал, что этот вопрос также можно решить с помощью Фибоначчи, и первые несколько ответов выглядят одинаково.

Мои вопросы: есть ли формальное математическое доказательство (или интуитивное объяснение) относительно того, почему эти два могут быть одинаковыми?или, если они одинаковы?

проблема подъема по лестнице - это проблема, которая требует от вас найти количество способов, которыми человек, делающий только один или два шага, может подняться по лестнице с n ступенями.Так как это просто способ сказать, сколько разных способов вы можете выстроить 1 и 2, что в сумме до n.Я решил вопросы таким образом.max_one и max_two - это максимальные числа 1 или 2, которые могут существовать, и я итерировал, сколько 2 может быть в строке, находя, как каждая отдельная строка может быть сформирована с учетом числа 2 (представленных как i), числитель - это сколько элементовв строке знаменатель - это сколько одинаковых элементов (сколько единиц, сколько единиц) в строке:

from math import factorial as fac
class Solution:
  def climbStairs(self, n):
    if n == 1:  return 1
    if n == 2:  return 2 
    max_two = n//2
    max_one = n
    ways = 0
    for i in range(0,max_two+1):
      ways += fac(max_one-i)/(fac(max_one-2*i) * fac(i))

    return int(ways)

Answer 1

Поздравляем!Вы заново открыли очень классную личность, включающую числа Фибоначчи.В частности, правило, которое вы нашли, это то, что наглядно продемонстрировано на этой картинке, где сложение членов треугольника Паскаля вдоль этих косых диагоналей возвращает последовательность Фибоначчи:

Чтобы увидетьпочему это так, обратите внимание, что каждое слагаемое в вашем суммировании равно (n - i) выбору i, которое является записью в строке (n - i), столбце i треугольника Паскаля.Каждое слагаемое в сумме соответствует перемещению вверх на одну строку и на один столбец, отсюда и угол на этих линиях.

Что касается доказательства, то аргумент, который вы обрисовали в общих чертах, по сути является основой двойного счетааргумент.Мы знаем, что числа Фибоначчи подсчитывают количество способов спуститься по лестничным пролетам, совершая шаги размеров один и два, что мы можем строго доказать по индукции.Кроме того, мы знаем, что ваше суммирование учитывает одно и то же количество, так как вы перечисляете все способы перехода по пути, используя шаги 0, 1, 2, 3, ... и т. Д. Второго размера.Поскольку мы рассчитываем одну и ту же величину двумя способами, эти два выражения должны быть равны.

Если этого недостаточно, вы можете формализовать это, используя доказательство по индукции, используя тождество (n выберите k)= (n-1 выбирает k) + (n-1 выбирает k-1) и разбивается на случаи, когда n четное, а n нечетное.

Надеюсь, это поможет!