Monday, 18 June 2007

co.combinatorics - Dyck paths on rectangles

Is a sum OK?



I am used to a different rotation of the paths. I think the paths you are looking for can also be described as all paths above the x-axis, with steps (1,1) and (1,-1), that starts at (0,0) and ends on the line x=y+n for some (x,y) from (n,0) to (n+m,m).



(If instead they end at the line x=n, we get the Ballot paths.)



Let B(n,k) be the Ballot numbers, B(n,k)= # paths from (0,0) to (n,k). Now, all paths must pass the line x=n. From there on it is just a binomial path, so the number of paths are
sum_{k=0,2,4,...,n} B(k,n)*( (n-m-k)/2 choose k/2)



(n choose k)= Binomial coefficient, n!/(k!(n-k)!)

No comments:

Post a Comment