math - 随机游走 N 次，只有第 N 次回到原来的地方，排列的次数是多少？

Question

假设一个粒子可以在 x 坐标上移动，这意味着它可以移动 0 到 1 或 1 到 2 或 N-1 到 N .etc，现在它从 0 开始，它可以每次向左或向右移动一步（例如当它到达 5 时，它可以向右移动到 6 或向左移动到 4)。并且经过N次移动，它到达了它原来的位置0，但是在中间它永远不会到达0，置换的次数是多少？

Answer 1

我认为您的问题的答案是加泰罗尼亚语数。

在维基页面中：

Cn 是长度为 2n 的 Dyck 字数。一个 Dyck 词是一个由 n 个 X 和 n 个 Y 组成的字符串，这样字符串的任何初始段中的 Y 都不会比 X 多（另见 Dyck 语言）。例如，以下是长度为 6 的 Dyck 词：

XXXYYY XXXXYY XYXYXY XXYYXY XXYXYY。

您可以认为 X 是向右走，Y 是向左走。

见http://en.wikipedia.org/wiki/Catalan_number