2 typo

Since that Mirko Visontai toled told me that the answer is ${a+b\choose a}/(a+b)$ if $\gcd(a,b)=1$. The proof is the following (with k=a and l=b):

The number of 0--1 vectors with $k$ 0's and $l$ 1's is ${k+l\choose k}$, so we have to prove that out of these vectors exactly $1/(k+l)$ fraction is an element of $L(k,l)$. The set of all vectors can be partitioned into equivalence classes. Two vectors $p$ and $q$ are equivalent if there is a cyclic shift that maps one into the other, i.e., if for some $j$, $p_i = q_{i+j}$ for all $i$. We will prove that exactly one element from each equivalence class will be in $L(k,l)$. This proves the statement as each class consists of $k+l$ elements because $gcd(k,k+l)=1$.

We can view each 0--1 sequence as a walk on $\mathbb R$ where each 0 is a $-l/(k+l)$ step and each 1 is a $+k/(k+l)$ step. Each $(k,l)$ walk starts and ends at zero and each walk reaches its maximum height exactly once, otherwise $ak + bl = 0$ for some $0 < a +b < k+l$ which would imply $\gcd(k,l) \neq 1$. If we take the cyclic shift that starts from the top'', we stay in the negative region throughout the walk, which corresponds to remaining under the diagonal in the lattice path case. Any other cyclic shift goes above zero, which corresponds to going above the diagonal at some point.

1

Since that Mirko Visontai toled me that the answer is ${a+b\choose a}/(a+b)$ if $\gcd(a,b)=1$. The proof is the following (with k=a and l=b):

The number of 0--1 vectors with $k$ 0's and $l$ 1's is ${k+l\choose k}$, so we have to prove that out of these vectors exactly $1/(k+l)$ fraction is an element of $L(k,l)$. The set of all vectors can be partitioned into equivalence classes. Two vectors $p$ and $q$ are equivalent if there is a cyclic shift that maps one into the other, i.e., if for some $j$, $p_i = q_{i+j}$ for all $i$. We will prove that exactly one element from each equivalence class will be in $L(k,l)$. This proves the statement as each class consists of $k+l$ elements because $gcd(k,k+l)=1$.

We can view each 0--1 sequence as a walk on $\mathbb R$ where each 0 is a $-l/(k+l)$ step and each 1 is a $+k/(k+l)$ step. Each $(k,l)$ walk starts and ends at zero and each walk reaches its maximum height exactly once, otherwise $ak + bl = 0$ for some $0 < a +b < k+l$ which would imply $\gcd(k,l) \neq 1$. If we take the cyclic shift that starts from the top'', we stay in the negative region throughout the walk, which corresponds to remaining under the diagonal in the lattice path case. Any other cyclic shift goes above zero, which corresponds to going above the diagonal at some point.