# Number of Motzkin paths with no horizontal steps at positive heights

combinatoricsreference-request

Let $$a(n,k)$$ be the number of all Motzkin paths of length $$n$$ with $$k$$ down-steps and no horizontal steps at positive heights. OEIS A008315 states that $$a(n,k)=\binom{n}{k}-\binom{n}{k-1}.$$
Where can I find a simple proof of this fact?

Let $$A(n,k)$$ be the set of Motzkin paths you describe.

Let $$B(n,k)$$ be the set of walks from $$(0,0)$$ to $$(n,n-2k)$$ whose steps are all $$(1,1)$$ or $$(1,-1)$$, and which never go below the $$x$$ axis.

Define $$f:A(n,k)\to B(n,k)$$ as follows. Given a Motzkin path, replace all of the horizontal steps on the ground with $$(1,1)$$ steps. For example,

                              /\/
/\               ==>    /\  /
/  \ _ _ /\ _           /  \/

A(9, 3)              B(9, 3)


I claim that $$f$$ is a bijection. The inverse map is this: given a path $$P$$ in $$B(n,k)$$, call an up step from $$(x,y)$$ to $$(x+1,y+1)$$ "critical" if $$P$$ never returns to a height of $$y$$ after that step. Replacing all critical up steps in $$P$$ with horizontal steps gives a path $$Q$$ in $$A(n,k)$$ for which $$f(Q)=P$$.

Finally, the reflection principle allows you to enumerate paths in $$B(n,k)$$ to be exactly $$\binom nk-\binom n{k-1}$$. That is, take the set of all $$\binom{n}k$$ paths from $$(0,0)$$ to $$(n,n-2k)$$, and subtract out the bad paths which at some point go below the $$x$$ axis. If you reflect that bad paths at the first time they dip below, you get a bijective correspondence to all paths from $$(0,0)$$ to $$(n,2k-n-2)$$, counted by $$\binom{n}{k-1}$$.