13
$\begingroup$

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} $.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Have you been able to translate the committee argument to the lattice path model (a $k$-subset of $\{1, 2, \dots, n\}$ corresponding to an ordered sequence of $n-k$ left turns and $k$ right turns as you walk from $(0,0)$)? The interpretation you get is not particularly natural in terms of paths, so I'm not sure there is going to be a 'simple' proof using the lattice path model. $\endgroup$ – Michael Joyce Dec 29 '13 at 23:37
  • 1
    $\begingroup$ The lattice path model is just the name I was using for your "block-walking" interpretation. To go from $(0,0)$ to $(n,k)$, you take a total of $n$ steps, $k$ to the right and $n-k$ to the left. So you can think of such a path as being determined by which $k$ of the steps $1,2,\dots,n$ that you go right (going left for the other $n-k$ steps). If you translate the committee argument to the block-walking interpretation, you'll get Ragnar's solution. $\endgroup$ – Michael Joyce Dec 30 '13 at 3:32
  • 2
    $\begingroup$ FWIW, while the term lattice path is somewhat standard, I don't think lattice path model is standard. I think your text probably used the term block-walking because it is more intuitive and less technical, certainly good things to have in terminology. If you want to include proofs that you think may be relevant to answering your question, the best place is probably as an edit to your original question. (Just indicate what part has been edited so people coming back to your question will know there is new information available.) $\endgroup$ – Michael Joyce Jan 2 '14 at 13:41
  • 1
    $\begingroup$ I have no idea what this bounty is looking for. $\endgroup$ – Phira Jan 16 '14 at 20:14
  • 1
    $\begingroup$ The literal interpretation of the question gives one of the existing answers, a more refined interpretation gives the other answer. Other approaches to the identity certainly exist, but they do not seem to answer the question, so presumably the bounty wants to modify the question a bit. $\endgroup$ – Phira Jan 16 '14 at 20:19
2
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ This is essentially the committee argument. Unfortunately, I don't think it translates very well to the lattice path model. $\endgroup$ – Michael Joyce Dec 29 '13 at 23:57
  • $\begingroup$ @MichaelJoyce Oh, I don't know exactly what the committee argument is, but this has at least something to do with the triangle. $\endgroup$ – Ragnar Dec 29 '13 at 23:59
  • $\begingroup$ I upvoted because I think you gave a nice explanation, but I think it is the same argument as the one OP mentioned. It is not clear whether OP is having difficulty translating that argument to lattice paths or is looking for a genuinely new argument. $\endgroup$ – Michael Joyce Dec 30 '13 at 0:48
  • $\begingroup$ @Ragnar, how would the argument change if we had $\binom{n}{k}\binom{m}{a}$ instead of $\binom{n}{k}\binom{k}{a}$? Is there any more significance to how the same $k$ appears in both $\binom{n}{k}$ and $\binom{k}{a}$ in this identity? $\endgroup$ – NaN Jan 17 '14 at 22:13
  • $\begingroup$ @IDentity, you first pick $k$ out of $n$, and then choose $a$ from those $k$ objects. If $m\neq k$, you couldn't say such a thing. $\endgroup$ – Ragnar Jan 18 '14 at 0:45
5
$\begingroup$

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.enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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