# Starting in the top left corner of a 2×2 grid,
# and only being able to move to the right and down,
# there are exactly 6 routes to the bottom right corner.
# How many such routes are there through a 20×20 grid?
def lattice_paths
a = (0..19).to_a
puts a.repeated_combination(a.length).to_a.length * 2
end
lattice_paths
This solved it, though it took my computer over an hour. I did a 3x3 grid by hand as a way check the solution in production.
Researching after-the-fact, I came upon this binomial coefficient:
f(n)=(2n-1; n)
But even after an hour of researching how to compute these, I still have no idea how to do it by hand, much less through Ruby.
The number of repeated combinations of length r of n things is equal to (n + r - 1; r). See this website (the section titled "Combinations with Repetition") for why.
In your code, r is the same as n, so you can write this as (2n - 1; n), which is what a.repeated_combination(a.length).to_a.length returns. Multiplying this value by 2 gives (2n; n) in this particular case (because (2x - 1; x) * 2 is equal to (2x; x) for all integers x), which is the correct answer.