Intuitive/combinatorial explanation of Delannoy summand 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?
 A: 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.
A: 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.
