Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
Could you really break the details down for a novice like me? It is not even apparent for me why ${a\choose i}{b\choose i}$ is the number of ways to arrange $a$ right-steps and $b$ up-steps such that exactly $i$ of the right-steps are followed by-up steps. I drew out an example we could perhaps reference. I will use the characters $D$, $R$, and $U$ to represent a diagonal move, a right move, and an upwards move respectively. My sequence is $\lbrack D,R,R,U,U,R,D,R,U,U\rbrack$. Could you explain your proof in terms of this sequence? I think the visual will really help me. Thanks. –  CodeKingPlusPlus Feb 27 '13 at 6:40
    
@CodeKing: I tried to describe how things work out in your example; hope that helps. –  joriki Feb 27 '13 at 8:01
    
Thanks so much! Near the bottom do you mean to say "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"? –  CodeKingPlusPlus Feb 27 '13 at 12:12
    
Also, what about the sequence U,U,U,U,U,U,R,R,R,R,R,R this takes me to the same point but I do not think it is counted by the method? –  CodeKingPlusPlus Feb 27 '13 at 12:22
    
@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$. –  joriki Feb 27 '13 at 13:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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