Finding the count of paths with K turns from corner to corner in a square box

calc_paths.py

'''
Based on https://math.stackexchange.com/a/1080170
'''

from functools import lru_cache, reduce
import operator

@lru_cache()
def fact(n):
  assert n >= 0
  if n < 1: return 1
  return n * fact(n-1)

@lru_cache()
def binom(a, b):
    af = reduce(operator.mul, (i for i in range(a-b+1, a+1)), 1)
    return af // fact(b)
  
n, k = 10, 5
print(sum((2 * binom(n-2, _k//2) * binom(n-2, (_k-1)//2)) for _k in range(1, k+1)))