Combinatorial interpretation of Delannoy numbers formula

Solution 1:

There are $\displaystyle\binom ai\binom bi$ different ways to arrange $a$ right-steps and $b$ up-steps such that exactly $i$ of the right-steps are followed by up-steps: Choose $i$ of the right-steps that are followed by up-steps and $i$ of the up-steps that are preceded by right-steps; then there's exactly one way to put all the remaining right-steps in front of right-steps or the end and all the remaining up-steps after up-steps or the beginning.

In each of these arrangements, you can choose independently for each of the $i$ combinations of right-step plus up-step whether to replace it by a diagonal step. That gives a factor of $2^i$, and in this manner you produce each path of right-steps, up-steps and diagonal steps exactly once.

[Edit in response to comment:]

In this case $a=b=6$ and $i=4$. I wonder whether making $a$ and $b$ equal is a good way to understand the proof, but I'll stick with your example. First resolve the diagonal steps back to combinations of right-step plus up-step to find the sequence of right-steps and up-steps from which your sequence originated: $RURRUURRURUU$. In this case you've chosen the first, third, fifth and sixth right-steps to be followed by up-steps and the first, second, fourth and fifth up-steps to be preceded by right-steps. Imagine those four combinations of right-step plus up-step fixed, and consider where you could place the remaining steps. The second right-step is between the first and third right-steps, and since it isn't supposed to be followed by an up-step, the only place to put it is right before the third right-step. By the same reasoning, the fourth right-step has to go right before the fifth right-step, the third up-step has to go right after the second up-step and the sixth up-step has to go right after the fifth up-step. Thus the choice of the right-steps followed by up-steps and the up-steps preceded by right-steps has fully determined the positions of the remaining steps. Now you have $i=4$ combinations of right-steps followed by up-steps, and for each of them you can choose whether to replace it by a diagonal step; you've chosen to replace the first and third pairs.