9
$\begingroup$

The Delannoy number $D(a,b)$ can be defined as the numbers of paths on $\mathbb Z^2$ from $(0,0)$ to $(a,b)$ using only steps $(0,1)$, $(1,0)$ and $(1,1)$.

It is straightforward to see that they follow the recursion (using either first-step or last step analysis, for example): $D(a,b)=D(a-1,b) + D(a,b-1)+D(a-1,b-1),$ where $D(0,b) = D(a,0)=1$.

I came to wonder if closed-form formulas existed for those numbers (actually, it was a riddle presented to me). The formula I came up with first fixes the number of diagonal steps in a given path, then counts the number of arrangements with a multinomial coefficient. This gives: $D(a,b) = \sum_{i=0}^{a\wedge b}\binom{a+b-i}{a-i,\,b-i,\,i}.$

However, a second formula is mentioned on MathWorld: $D(a,b) = \sum_{i=0}^{a\wedge b}2^i\binom{a}{i}\binom{b}{i},$

and I was wondering if it had a similarly simple combinatorial interpretation.

1 Answers 1

10

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.

  • 1
    @CodeKing: Yes, thanks for the correction. I don't understand why you think there's$a$problem with this sequence. In this case no right-steps are followed by up-steps and no up-steps are preceded by right-steps, so $i=0$. There is exactly one such sequence, and indeed $2^0\binom a0\binom b0=1$.2013-02-27