What is the number of lattice paths from $(0,0)$ to $(n, 0)$ where each step the path can move $(.5, 1)$, $(.5, -1)$, $(1,0)$ and the first down step must be after the last up step?

I tried reasoning as follows: if k is the number of up steps, then k must also be the number of down steps. Since all up steps must be before the first down step there is only one way to order the up and down steps with respect to one another. Since each of these 2k steps are of length $.5$ we are left with $n-k$ flat steps. We then use stars and bars to say that the number for paths is ${n+k \choose 2k}$. Summing over all values for k we get $\sum\limits_{k=0}^{n}{n+k \choose 2k}$. Am I doing this right? Is there a closed form?

  • $\begingroup$ What is the letter $l$ ? $\endgroup$ – Hector Blandin Apr 8 '18 at 16:19

You are correct, except I don't see why you need to use stars and bars to get the expression $\binom {n+k}{2k}$: if you take $k$ up steps, $k$ down steps, and $n-k$ horizontal steps, then just the usual notion of binomial coefficients is enough to show that there are $\binom{n+k}{2k}$ ways to choose which of the steps are up or down steps (and then it is uniquely determined which ones are up and which ones are down).

The expression $$ \sum_{k \ge 0} \binom{n+k}{2k} $$ does have a closed form; if you compute its value for the first few values of $n$, you will see that $$ \sum_{k \ge 0} \binom{n+k}{2k} = F_{2n+1} $$ (that is, the $(2n+1)^{\text{th}}$ Fibonacci number).

You can prove this identity algebraically, but it might be a better strategy to find a different combinatorial argument. As a hint, a well-known problem counted by the Fibonacci numbers is the number of ways to tile a $1 \times n$ rectangle by $1 \times 1$ and $1 \times 2$ tiles.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.