Let $A=[0,0]$ and $B=[n,n]$. In how many ways can we go from $A$ to $B$, if we always want to go from lattice point to its neighbour (i.e. point with one coordinate the same and one smaller or bigger by one), we never want to visit the same point twice and we want our path to have length $2n+2$? (For example, path $[0,0],[0,1],[-1,1],[-1,2],[0,2],[1,2],[2,2],[2,3],[3,3]$ is one of the paths for $n=3$)
Problem
Source: Czech and Slovak Olympiad 2015, National Round, Problem 2
Tags: combinatorics, lattice paths
skyletter
11.01.2016 12:51
isnt it just (2n+2)！/（（n+1)！）^2
yuusan
30.08.2016 18:57
Imagine a robot at (0,0) and we are attempting to program it to get to (n,n) with 2n+2 steps with just the commands RLUD for right left up down. Then the "code" will have n Us, n Rs, and either 1 L and 1more R or 1D and 1 more U. Each code corresponds to exactly one possible path. The number of all possible paths of length 2n+2 is therefore the number of permutations of n+1 Us n Rs 1D plus the number of permutations of n Us n+1Rs and 1L. however, with the constraint that you cannot return to a point previously visited, we have to make sure that an R is not followed by L and vice versa. We notice this is the only way you can return to a previous point with only 1 move to the left or down. therefore, L must be surrounded by Us and D must be surrounded by Rs. for example RURRURDRURURUUUU We separate into 2 cases whether L (or D) happens at the ends of the code or not If L (or D) comes on the ends of the code the preceding letter must be R (or U). The other n-1 Rs and n+1Us may freely arrange themselves; therefore the possible arrangements are 2 (L or D)*2 (First letter or last)* (2n)!/(n+1)!(n-1)! If L (or D) does not come on the ends of the code both the preceding letter and the succeeding letter must be R (or U). The other n-2 Rs and n+1 Us may freely arrange themselves; therefore the possible arrangements are 2 (L or D) * n (number of possible positions of L or D) * (2n-1)!/(n+1)!(n-2)! = 2n!/ (n+1)!(n-2)! So the total number of possible paths are 4* (2n)!/(n+1)!(n-1)!+2n!/(n+1)!(n-2)!=(4+n-1)*2n!/(n+1)!(n-1)!= (n+3)*2n!/(n+1)!(n-2)!