# 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
这解决了它，虽然我的电脑花了一个多小时。我手工做了一个 3x3 网格，以检查生产中的解决方案。
事后研究，我发现了这个二项式系数：
f(n)=(2n-1; n)
但即使经过一个小时的研究如何计算这些，我仍然不知道如何手动完成，更不用说通过 Ruby。
r事物长度的重复组合数n等于(n + r - 1; r)。请参阅此网站（标题为“与重复组合”的部分）了解原因。
在您的代码中，r与 相同n，因此您可以将其写为(2n - 1; n)，这就是a.repeated_combination(a.length).to_a.length返回的内容。(2n; n)在这种特殊情况下，将此值乘以 2 （因为对于所有整数(2x - 1; x) * 2都等于），这是正确的答案。(2x; x)x
@Brad 是对的（或几乎是对的——不确定）。这就是为什么。对于nxn网格（即n行和n列），从左上角到右下角的每条路径都有n-1向下移动和n-1向右移动。此类路径的数量等于n-1从总移动中选择正确移动（或向下移动）的方式的数量2*(n-1)：
(total moves)!/(right moves)!*(total moves - right moves)!
#=> (total moves)!/(right moves)!**2
#=> (2*(n-1))!/(n-1)!**2
对于n=20，这是：
38!/19!**2
对于n=21：
40!/20!**2
这是@Brad 的回答。对于n=3，有：
4!/2!**2 #=> 6
路径。问题指出“2x2”网格“有 6 条路径，所以我必须将其视为“3x3”网格。我希望这种解释上的差异也解释了为什么布拉德的答案与我的n=21情况相对应。
我不久前在 Ruby 中解决了这个问题。
我不知道它是如何工作的，但它给出了正确的答案。
puts (1..40).inject(:*) / (1..20).inject(:*) ** 2