10
$\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.

$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – CodeKingPlusPlus
    Feb 27, 2013 at 6:40
  • $\begingroup$ @CodeKing: I tried to describe how things work out in your example; hope that helps. $\endgroup$
    – joriki
    Feb 27, 2013 at 8:01
  • $\begingroup$ 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"? $\endgroup$
    – CodeKingPlusPlus
    Feb 27, 2013 at 12:12
  • $\begingroup$ 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? $\endgroup$
    – CodeKingPlusPlus
    Feb 27, 2013 at 12:22
  • 1
    $\begingroup$ @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$. $\endgroup$
    – joriki
    Feb 27, 2013 at 13:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .