Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

Question

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$

is the following "committee" argument, which seems the most common.

There are $\binom{n}{k}$ ways to select $k$ from a set of $n$ to go on the committee, and then $\binom{k}{a}$ ways to select $a$ from that committee of $k$ to go on a sub-committee of size $a$. This is equivalent to changing the order of selection to first choosing the sub-committee of $a$ from the set of $n$, then choosing the remaining $k-a$ on the committee from $n-a$ possible.

For anyone familiar with the "block-walking" interpretation of Pascal's triangle, how would you show the same identity with a block-walking argument?

For those not familiar with block-walking, please observe the following without a rigorous argument. There are $\binom{4}{2}$ possible paths to reach the point $(4,2)$ in the triangle below, since every path to $(4,2)$ requires $2$ traversals in the direction right out of $4$ traversals total. As another example, there are $\binom{2}{0}$ paths to reach $(2,0)$. In general,there are $\binom{n}{k}$ ways to reach the point $(n,k$).

An example of a "block-walking" combinatorial argument for Pascal's identity might be as follows. Observe that the count of possible ways to reach a point $(n,k)$ is exactly the sum of the possible ways to reach the two points which lead to it, namely $(n-1,k-1), (n-1,k)$. To say this algebraically, $\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k} $.

Answer 1

We are going to look at routes from the top of the triangle with length $n$ and $k$ steps to the left (and $n-k$ to the right). Also, assume there are $a$ 'special' steps to the left. (The set of special steps is a subset of the set of all steps to the left.) We are going to calculate the number of routes in two ways.

First, we just look at all routes without considering the special steps. There are $\binom nk$ such routes. For each route we have to select $a$ out of $k$ left steps to be special. We can do this in $\binom ka$ ways for each route, so altogether, we get $\binom nk\binom ka$.

Now, suppose we first select $a$ out of $n$ steps to be special steps (to the left). This gives $\binom na$ possibilities (from the definition of the binomial). Now, from the remaining $n-a$ steps, we have to select $k-a$ steps to the left: $\binom {n-a}{k-a}$ possibilities.
Together, we get the following equality: $$ \binom nk\binom ka=\binom na\binom{n-a}{k-a} $$

(does anybody know how to make all binomials the same size?)

Answer 2

I'm not able to come up with an argument that is fundamentally different from the "committee argument", but it is possible to cast the entire proof in geometric terms if one is willing to move into the third dimension.

Consider a three-dimensional grid analogous to your two-dimensional one. Your grid is a quadrant of an infinite two-dimensional grid; the three-dimensional analogue would be an octant of an infinite three-dimensional grid. In your grid, there are two directions in which one can move, left and right. A point in your grid is given by coordinates $(n,k),$ where $n\ge0$ is the total number of steps and $k$ ($0\le k\le n$) is the number of right steps. In the three-dimensional version, there are three directions in which one can move, which we will call left, right, and back. (Think of "back" as the direction into the page.) A point in the grid can be given coordinates $(n,k,a),$ where $n$ is the total number of steps, $k$ ($0\le k\le n$) is the number of left and right steps (that is, non-back steps), and $a$ ($0\le a\le k$) is the number of left steps.

The two sides of your identity both equal the number of three-dimensional grid paths joining $(0,0,0)$ to $(n,k,a),$ and correspond to different ways of decomposing a three-dimensional grid path into two two-dimensional grid paths. In two dimensions, the two directions of movement might be given coordinates $$ L:\ \left(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right),\qquad R:\ \left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right). $$ In three dimensions, the three directions might be given coordinates $$ L:\ \left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right),\qquad R:\ \left(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right),\qquad B:\ \left(0,-\sqrt{\frac{2}{3}},-\frac{1}{\sqrt{3}}\right). $$ If we project out the $x$-coordinate in this coordinate system, then left and right steps look the same: both correspond to a move which we might call "front", $$ F:\ \left(0,\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right). $$ A path from $(0,0,0)$ to $(n,k,a)$ then consists of $k$ front steps and $n-k$ back steps. The number of such paths is $\binom{n}{k}.$ If we project out the back coordinate, that is, we project onto the plane of the left and right steps, then we effectively remove all back steps from the path. Such a path then consists of $k$ steps, $a$ of which are left steps, and $k-a$ of which are right steps. There are $\binom{k}{a}$ such paths. The number of three-dimensional paths is given by the product of the numbers of paths in these two projections, which is the left side of your identity.

To get the right side of the identity, we perform a projection so that right and back steps look like each other and left steps are unchanged. (It's not terribly relevant to the combinatorics, but this projection is achieved by the map $v\mapsto v-(n\cdot v)n$ where $$ n=\left(\frac{1}{2},-\frac{\sqrt{3}}{2},0\right) $$ is the unit vector orthogonal to the $L$ direction and the $z$ axis. Under this projection, the $R$ and $B$ directions both map to $$ N:\ \left(-\frac{1}{2\sqrt{2}},-\frac{1}{2\sqrt{6}},-\frac{1}{\sqrt{3}}\right). $$ Here $N$ stands for "non-left".) The three-dimensional path then projects to a path consisting of $a$ left steps and $n-a$ non-left steps. There are $\binom{n}{a}$ such paths. If we project onto the plane of the right and back steps, which effectively removes left steps, we are left with a path of $n-a$ steps, $k-a$ of which are right steps and $n-k$ of which are back steps. There are $\binom{n-a}{k-a}$ such paths. Again, the number of three-dimensional paths is given by the product of the numbers of paths in these two projections.

This is, of course, the committee argument: the left and right steps are the committee members, and the left steps are the special committee members. The back steps are the non-members of the committee.

Added: In my opinion, the best way to look a the identity was given in Marc van Leeuwen's answer here. Let $b=k-a$ and let $c=n-k$ so that $k=a+b$ and $n=a+b+c.$ Then the identity becomes $$\binom{n}{a+b}\binom{a+b}{a}=\binom{n}{a}\binom{n-a}{b},$$ which can be rewritten as $$\binom{n}{c}\binom{n-c}{a}=\binom{n}{a}\binom{n-a}{b}.$$ The latter consists of two pieces of the six-way identity $$\begin{aligned} \binom{n}{a}\binom{n-a}{b}=\binom{n}{a}\binom{n-a}{c}&=\binom{n}{b}\binom{n-b}{a}=\binom{n}{b}\binom{n-b}{c}\\ &=\binom{n}{c}\binom{n-c}{a}=\binom{n}{c}\binom{n-c}{b} \end{aligned}$$ in which the roles of $a,$ $b,$ and $c$ have been permuted in all possible ways. These correspond to six different ways of writing the trinomial coefficient $$ \binom{n}{a,b,c}=\frac{n!}{a!\,b!\,c!}. $$ The six-way identity is easy to show since all six expressions telescope to give the right hand side of the formula above. For example, $$ \binom{n}{b}\binom{n-b}{a}=\frac{n!}{b!(n-b)!}\frac{(n-b)!}{a!(n-a-b)!}=\frac{n!}{a!\,b!\,c!}, $$ where we have used $n-a-b=c.$ The same proof works for all six expressions.

In terms of the geometric picture I outlined above, the first two of the six expressions correspond to projecting so that right and back steps look alike, and then projecting onto the plane of right and back steps; the second two correspond to projecting so that back and left steps look alike, and then projecting onto the plane of back and left steps; the last two correspond to projecting so that left and right steps look alike, and then projecting onto the plane of left and right steps. In each pair, both expressions count the same thing: for example, in the first pair, $\binom{n-a}{b}$ and $\binom{n-a}{c}$ both count the number of paths consisting of $b$ right steps and $c$ back steps.

Note that the $6=3!$ telescoping expressions for the trinomial coefficient become $\ell!$ expressions in the case of multinomial coefficients (with $n=a_1+a_2+\ldots+a_\ell$): $$ \begin{aligned} &\binom{n}{a_1,a_2,\ldots,a_\ell}=\frac{n!}{a_1!\,a_2!\,\ldots,a_\ell!}\\ &\quad=\frac{n!}{a_1!(n-a_1)!}\frac{(n-a_1)!}{a_2!(n-a_1-a_2)!}\frac{(n-a_1-a_2)!}{a_3!(n-a_1-a_2-a_3)!}\ldots\frac{(n-a_1-\ldots-a_{\ell-1})!}{a_\ell!(n-a_1-\ldots-a_\ell)!}\\ &\quad=\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}\ldots\binom{n-a_1-\ldots-a_{\ell-1}}{a_\ell}. \end{aligned} $$ Observe that the $\ell^\text{th}$ binomial coefficient in the product always equals $1$ and can be omitted since $n-a_1-\ldots-a_{\ell-1}=a_\ell.$ This is what was done in your original identity. Permutations of the $a_j$ give $\ell!$ different expressions for the multinomomial coefficient. Such expressions should be interpretable in terms of different series of projections of an $\ell$-dimensional grid.

Further comments: The difficulty with interpreting this identity geometrically is that it contains products of binomial coefficients. The product could represent concatenation of paths, but the set of paths described on the left doesn't look much like the set of paths described on the right. (They have different ending points, different numbers of steps, and so on.) One can devise a bijection between the set of paths counted by the left side and the set of paths counted by the right side, but this is essentially the committee argument, and isn't at all natural—at least the way I came up with isn't. My answer was an attempt to interpret multiplication in terms of combining different projections rather than in terms of concatenation. I haven't yet been able to come up with any other geometrical interpretation of multiplication.