智力之谜

Question

考虑笛卡尔协调系统中的一个点P(n，n) .机器人必须从起源开始，到达这一点。机器人所能采取的唯一步骤是：

• 1单位权利
• 一个单位上升。

机器人能走多少条不同的路径到达P点？

有到点P的最佳路径吗？(向上和正确的步骤都要付出同样的代价)。

Answer 1

路径的总数是

(2n choose n)

因为您必须使n正确的步骤和n向上的步骤结束在点(n,n)，但您的顺序是不相关的步骤。

所以有2n的总步骤，其中n是对的，n是向上的。以(2n choose n)方式选择正确步骤的位置，其余步骤必须是向上步骤。

没有哪一条路径比任何其他路径更好，因为所有路径都使用相同数量的向上和正确的步骤(都是n)。

Answer 2

滚动维基百科的这篇文章(加泰罗尼亚数字)，直到您到达以下图片。答案就在那里。

​

​

因此，路径的总数是

​

​

注:此论坛仅适用于单调路径，而不是交叉对角线。如果你想让交叉的对角线，它需要改变一点。)为此使用递归:)

希望它有用。

Answer 3

它必须是(2n!)/(n!*n!)。

解释:

你必须从原点(0，0)到(n，n)，假设v是垂直向上的1单位，h是水平向右的1单位。所有路径看起来都是这样的-- {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........)的v和h分布在v的数的长度+h的数上，这必须是

N+n= 2n。

现在，在2n个地方，路径总数将是vs和hs的组合，等于

(n+n)/(n*n！)

因为v和h是重复的。如果有其他单位，如a或b，它也会被考虑在内。我认为它不会是一个加泰罗尼亚数。Rgds，软