Search code examples
mathrandom-walk

random walk N times and only Nth return to the orignal place, what's the number of permulation?

suppose a partical can move on x-coordinate, which means it can move 0 to 1 or 1 to 2 or N-1 to N .etc, now it starts with 0, it can move one step every time, left or right (e.g. when it reaches 5, it can move right to 6 or left to 4). and after N times of moving, it reaches it original place 0, however, it never reaches 0 in the intermidate, what the number of the permulation?

Solution

  • I think the answer of your question is Catalan number.

    In wiki page:

    Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:

    XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

    You can consider X is go right and Y is go left.

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