Intuitive/combinatorial explanation of Delannoy summand

Question

The $n$th central Delannoy number $D_n$ is the number of lattice walks from $(0,0)$ to $(n,n)$ taking only steps up, right, and northeast, to neighbor lattice points. From Wikipedia: $$D_n=\sum_{k=0}^n{n \choose k}{{n+k} \choose k}.$$ I am wondering if there is an intuitive/combinatorial explanation as to why we are summing ${n \choose k}{{n+k} \choose k}$. That is, is there an intuition behind what it is counting?

Answer 1

Consider a Delannoy walk from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that has $k$ steps to the right; it must also have $k$ steps up and $n-k$ diagonal steps for a total of $n+k$ steps. There are $\binom{n+k}k$ ways to choose which of the $n+k$ steps are to be to the right, and there are then $\binom{n}k$ ways to choose which of the remaining $n$ steps are to be up. Thus, there are $\binom{n}k\binom{n+k}k$ Delannoy walks from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that have $k$ steps to the right, and summing over the possible values of $k$ yields the result.

Answer 2

We have $k$ right steps, $k$ up steps and $n-k$ diagonal steps.

The multinomial:

$$\binom{k+k+n-k}{k;k;n-k}=\binom{n+k}{k;k;n-k}$$

then gives the number of ways of creating $n+k$ steps with the appropriate number of steps in each direction.

If we use the substitution $k\leftrightarrow n-k$, then we get:

$$\binom{n}{k}\binom{n-2k}{n-k}$$

but now we have $n-k$ steps right, $n-k$ steps up, and $k$ steps diagonally, for a total of $2n-k$ steps. The first term now represents the column position of the diagonal elements, and is therefore perhaps easier to see.

The original multinomial also equals:

$$\binom{n+k}{n-k}\binom{2k}{k}$$

which also has the first term representing the positioning of the diagonal elements.