Jtdylktuy

In symbols, the identity is

$$left({n-1atop m-1}right)left({natop m+1}right)left({n+1atop m}right) =
left({natop m-1}right)left({n-1atop m}right)left({n+1atop m+1}right).$$

The usual combinatorial interpretation of a binomial coefficient $left({natop m}right)$ is that it counts subsets of size $m$ from a set of size $n$. Multiplication is usually interpreted as mutually exclusive choice ($f(n)g(n)$ counts the process of picking $f(n)$ configurations, then picking (independently) $g(n)$ items.

Putting this together, the LHS counts subsets of size $m-1$ from a set of size $n-1$, then subsets of size $m$ from an (independent) set of size $n+1$, then (again independently) subsets of size $m+1$ from a set of size $n$. This corresponds one-to-one with the RHS because the things counted by the LHS can be counted in a different way by the RHS: For the RHS distinguish an element of the $n$ set and one of the $n+1$ set. What's left over for those two sets can be chosen by $left({n-1atop (m+1)-1}right)$ and $left({(n+1)-1atop m-1}right)$ respectively, and then the two distinguished elements can be included to be (possibly) chosen in the $n-1$ set to account for $left({(n-1) +2 atop (m-1)+2}right)$.

To be clearer about the combinatorial interpretation, there are three sets, of size $n-1$, $n$, and $n+1$, from which you choose subsets of size $m-1$, $m+1$, and $m$, respectively. Another way to count this situation is to, take 1 item each out of the $n$ and $n+1$ sets, and add them to the $n-1$ set. So now you're counting out of sets of size $n+1$, $n-1$, and $n$, from which you choose subsets of size $m+1$, $m$, and $m-1$, respectively.

I've left some questions as comments to Mitch's answer, and am hoping that my confusions about that answer will get cleared up soon. Meanwhile, I started to think about how I would approach this problem. I don't have a satisfying answer yet; the best I've been able to come up with requires introducing an additional factor on both sides of the identity. The modified identity (which is algebraically equivalent to the unmodified one) has a clear combinatorial meaning, but I don't yet see a way to interpret the unmodified identity in combinatorial terms.

It's nice to generalize the identity slightly. Starting with the identity as written in Mitch's answer,
$$
binom{n - 1}{m - 1} binom{n}{m + 1} binom{n + 1}{m} =
binom{n}{m - 1} binom{n - 1}{m} binom{n + 1}{m + 1},
$$
we replace the $1$ with $r$ everywhere to obtain
$$
binom{n - r}{m - r} binom{n}{m + r} binom{n + r}{m} =
binom{n}{m - r} binom{n - r}{m} binom{n + r}{m + r}.
$$
This is also an identity, as we show below. Just as in the original identity, the binomial coefficients that appear form the vertices of a hexagon (which we might call the radius-$r$ hexagon) centered at $binom{n}{m}$ in Pascal's triangle. Note that the GCD property mentioned in the original post only holds for $r=1,$ while the identity holds for all $r.$ We concern ourselves only with the identity.

We prove the radius-$r$ identity starting from an elementary identity relating different ways of representing the trinomial coefficient as a product of binomial coefficients:
$$
binom{n}{k}binom{k}{a}=binom{n}{a}binom{n-a}{k-a}=binom{n}{n-k,k-a,a}.
$$
This has a combinatorial interpretation, as discussed here. The following three variants of this identity are useful here:
$$
begin{aligned}
binom{n}{r}binom{n-r}{m-r}&=binom{n-m+r}{r}binom{n}{m-r}\
binom{m+r}{r}binom{n}{m+r}&=binom{n}{r}binom{n-r}{m}\
binom{n-m+r}{r}binom{n+r}{m}&=binom{m+r}{r}binom{n+r}{m+r}.
end{aligned}
$$
The rightmost factors on the left side of these equations match the three factors on the left side of the identity, while the rightmost factors on the right side of these equations match the three factors on the right side of the identity. Furthermore, the leftmost factors on the left side of these equations are the same, but permuted, as the leftmost factors on the right side of these equations.

These observations suggest the idea of multiplying both sides of the radius-$r$ identity by
$$
binom{n}{r}binom{m+r}{r}binom{n-m+r}{r}
$$
to get
$$
begin{aligned}
&binom{n}{r}binom{n - r}{m - r} cdot binom{m+r}{r}binom{n}{m + r} cdot binom{n-m+r}{r}binom{n + r}{m}\
&qquad= binom{n-m+r}{r}binom{n}{m - r} cdot binom{n}{r}binom{n - r}{m} cdot binom{m+r}{r}binom{n + r}{m + r}.
end{aligned}
$$
The two sides of this identity can be thought of as different ways of answering the following question: there are $n$ students, $n$ teachers, and $n+r$ administrators. A committee is to be formed having $m$ students $m+r$ teachers, and $m+r$ administrators. From this committee, a subcommittee is to be formed having $r$ students, $r$ teachers, and $r$ administrators. In how many ways can this be done?

On the left side, this is accomplished by

• choosing $r$ students to be on the subcommittee, then choosing $m-r$ additional students to fill out the committee,


• choosing $m+r$ teachers to be on the committee, then from these choosing $r$ to be on the subcommittee,


• choosing $m$ administrators to be on the committee but not the subcommittee, then choosing $r$ additional administrators to be on the subcommittee.

On the right side, it is accomplished by

• choosing $m-r$ students to be on the committee but not the subcommittee, then choosing $r$ additional students to be on the subcommittee,


• choosing $r$ teachers to be on the subcommittee, then choosing $m$ additional teachers to fill out the committee,


• choosing $m+r$ administrators to be on the committee, then from these choosing $r$ to be on the subcommittee.

Clearly we get the same set of committee and subcommittee assignments either way, so the two sides must be equal.

This proof is unsatisfactory since we had to multiply the identity by the extraneous factor
$$
binom{n}{r}binom{m+r}{r}binom{n-m+r}{r}
$$
in order to be able to state our combinatorial interpretation. I have not yet been able to find a method that avoids this.

Added 26 January 2014: I should have looked at the linked pdf in the question before posting. There the identity is further generalized to
$$
binom{n - r}{m - s} binom{n}{m + r} binom{n + s}{m} =
binom{n}{m - s} binom{n - r}{m} binom{n + s}{m + r},qquadqquad(*)
$$
which corresponds to a hexagon with side lengths alternately $r$ and $s.$ The proof above works with small modifications. Multiply both sides by
$$
binom{n}{r}binom{m+r}{r}binom{n-m+s}{r}
$$
to get
$$
begin{aligned}
&binom{n}{r}binom{n - r}{m - s} cdot binom{m+r}{r}binom{n}{m + r} cdot binom{n-m+s}{r}binom{n + s}{m}\
&qquad= binom{n-m+s}{r}binom{n}{m - s} cdot binom{n}{r}binom{n - r}{m} cdot binom{m+r}{r}binom{n + s}{m + r}.
end{aligned}
$$
The interpretation of the three "trinomial pairs" that appear on left and on right is similar to before.

Added 8 February 2014: There are, in fact two similar and related, but distinct, proofs along these lines. After permuting factors on both sides of the identity $(*)$ in the section above to get
$$
binom{n - r}{m - s} binom{n + s}{m} binom{n}{m + r} =
binom{n - r}{m} binom{n}{m - s} binom{n + s}{m + r},
$$
we multiply both sides by
$$
binom{n-m-r+s}{s}binom{m}{s}binom{n+s}{s}
$$
and obtain
$$
begin{aligned}
&binom{n-m-r+s}{s}binom{n - r}{m - s} cdot binom{m}{s}binom{n + s}{m} cdot binom{n+s}{s}binom{n}{m + r}\
&qquad = binom{m}{s}binom{n - r}{m} cdot binom{n+s}{s}binom{n}{m - s} cdot binom{n-m-r+s}{s}binom{n + s}{m + r}.
end{aligned}
$$
In the previous section, the counting problem had the parameters,
$$
begin{array}{l|ccc}
& text{number} & text{number on} & text{number on}\
& text{in pool} & text{committee} & text{subcommittee}\
hline
text{students} & n & m+r-s & r\
text{teachers} & n & m+r & r\
text{administrators} & n+s & m+r & r\
end{array}
$$
while in this section, the parameters are
$$
begin{array}{l|ccc}
& text{number} & text{number on} & text{number on}\
& text{in pool} & text{committee} & text{subcommittee}\
hline
text{students} & n-r & m & s\
text{teachers} & n+s & m & s\
text{administrators} & n+s & m+r+s & s\
end{array}
$$

The two proofs both relate to the hexagon with side-lengths alternating between $r$ and $s$. The proof in the previous section is obtained by relating the binomial coefficients corresponding to endpoints of the sides of length $r,$ while the proof in this section is obtained by relating the binomial coefficients corresponding to endpoints of the sides of length $s.$

Added 10 October 2018: I missed a third proof, which is similar to the previous two in that all three involve converting the binomial coefficients to trinomial coefficients. After permuting factors again to get
$$
binom{n}{m + r} binom{n - r}{m - s} binom{n + s}{m} =
binom{n}{m - s} binom{n + s}{m + r} binom{n - r}{m},
$$
we multiply both sides by
$$
binom{m+r}{r+s}binom{n+s}{r+s}binom{n-m+s}{r+s}
$$
and obtain
$$
begin{aligned}
&binom{n}{m + r}binom{m+r}{r+s} cdot binom{n+s}{r+s}binom{n - r}{m - s} cdot binom{n + s}{m}binom{n-m+s}{r+s}\
&qquad=
binom{n}{m - s}binom{n-m+s}{r+s} cdot binom{n + s}{m + r}binom{m+r}{r+s} cdot binom{n+s}{r+s}binom{n - r}{m},
end{aligned}
$$
In this proof, the parameters of the counting problem are
$$
begin{array}{l|ccc}
& text{number} & text{number on} & text{number on}\
& text{in pool} & text{committee} & text{subcommittee}\
hline
text{students} & n & m+r & r+s\
text{teachers} & n+s & m+r & r+s\
text{administrators} & n+s & m+r+s & r+s\
end{array}
$$
In this version, the two hexagon vertices associated with a given trinomial coefficient are diametrically opposite, rather than adjacent along sides of length $r$ or $s$.

Added 4 December 2018: I can't resist adding a generalization of the identity for the multinomial coefficients that may shed some light on the structure of the identity in the binomial case and on its three different proofs.

Let $ellge2$, let $k_1$, $k_2$, ..., $k_ell$, $r_0<r_1<ldots<r_ell$ be integers such that $k_i+r_0ge0$ for all $iin{1,2,ldots,ell}$. Set $n=sum_{i=1}^ell k_i+sum_{i=0}^ell r_i$. Use $pi$ to denote a permutation of $(r_0,r_1,ldots,r_ell)$. Then we have the identity
$$
prod_{text{sgn}(pi)=1}binom{n-pi(r_0)}{k_1+pi(r_1),ldots,k_ell+pi(r_ell)}=prod_{text{sgn}(pi)=-1}binom{n-pi(r_0)}{k_1+pi(r_1),ldots,k_ell+pi(r_ell)}.
$$

Proof: Observe that the definition of $n$ and the restrictions on the $r_i$ guarantee that the multinomial coefficients are well-formed, that is, that the lower numbers in each coefficient sum to the upper number and that the lower numbers are all non-negative. The statement may be proved by observing that if both sides are multiplied by a suitable quantity, then both reduce to the same $left(frac{1}{2}(ell+1)!right)$-fold product of $(ell+1)$-nomial coefficients.

To find a suitable multiplier, choose a pair of indices $i<j$ from the set ${0,1,ldots,ell}$. The multiplier will be a product of binomial coefficients, one associated to each factor in the identity. For each multinomial coefficient in the identity (on either side), the parameter $r_j$ will appear in exactly one argument of the coefficient. If it appears in one of the lower arguments, that is, we have $k_a+r_j$ as a lower argument, introduce the binomial coefficient
$$
binom{k_a+r_j}{k_a+r_i,r_j-r_i}.
$$
If it appears in the upper argument, that is, if the upper argument is $n-r_j$, then introduce the binomial coefficient
$$
binom{n-r_i}{n-r_j,r_j-r_i}.
$$
The product of the binomial coefficients so introduced is the same on each of the two sides since each of the binomial coefficients
$$
binom{n-r_i}{n-r_j,r_j-r_i}, binom{k_1+r_j}{k_1+r_i,r_j-r_i}, ldots, binom{k_ell+r_j}{k_ell+r_i,r_j-r_i}
$$
will be introduced exactly $frac{1}{2}ell!$ times on the left and the same number of times on the right. Hence we have found equal multipliers for the two sides.

To show that when the multiplier is included, the two sides reduce to the same quantity, observe that for the multinomial coefficient in the identity associated with the permutation $pi$, there is a corresponding multinomial coefficient of opposite parity, obtained by following the permutation $pi$ with the swap $(r_ir_j)$. The result now follows from the fact that when the introduced binomial coefficients are included, these $ell$-nomials become equal $(ell+1)$-nomials. Indeed,
begin{align*}
&binom{ldots}{ldots, k_a+r_i, ldots, k_b+r_j, ldots} binom{k_b+r_j}{k_b+r_i,r_j-r_i}\
&quad=binom{ldots}{ldots, k_a+r_j, ldots, k_b+r_i, ldots} binom{k_a+r_j}{k_a+r_i,r_j-r_i}\
&quad=binom{ldots}{r_j-r_i, ldots, k_a+r_i, ldots, k_b+r_i, ldots}
end{align*}
when $r_i$ and $r_j$ both appear in lower arguments, while
begin{align*}
&binom{n-r_i}{ldots, k_a+r_j, ldots} binom{k_b+r_j}{k_b+r_i,r_j-r_i}\
&quad=binom{n-r_j}{ldots, k_a+r_i, ldots} binom{n-r_i}{n-r_i,r_j-r_i}\
&quad=binom{n-r_i}{r_j-r_i, ldots, k_a+r_i, ldots}
end{align*}
when one of them appears in the upper argument. $square$

Note that the original hexagonal identity is the case $ell=2$, $r_1=-1$, $r_2=0$, $r_3=1$ and that the generalized hexagonal identity is the case $ell=2$, $r_1=-s$, $r_2=0$, $r_3=r$. That there are three binomial coefficients on each side of the hexagonal identity reflects the fact that there are $frac{1}{2}(ell+1)!=3$ even permutations and the same number of odd permutations.

The proof of the multinomial version of the identity involved the arbitrary choice of the two indices $i$ and $j$. This means that there are, in fact $binom{ell+1}{2}$ different ways of constructing this proof, each with its own combinatorial interpretation. As before, these are not combinatorial proofs, since they involve the introduction of the multiplier. That there were three similar proofs in the hexagonal case reflects that fact that, when $ell=2$, there are are $binom{ell+1}{2}=3$ ways of choosing $i$ and $j$.

It is worth pointing out that the hexagonal formation in the original Pascal's triangle identity is a translation of the permutohedron of ${r_0,r_1,r_2}$. The higher multinomial identities are associated with formations in Pascal's pyramid or its higher-dimensional generalizations taking the shape of some higher-dimensional polytope. When $ell=3$, for example, the permutations of ${r_0,r_1,r_2,r_3}$ form the vertices of a truncated octahedron.

Finally, observe that there is a redundancy in the parameters that appear in the statement of the general identity. In particular $r_0$ may be eliminated by defining
$$
begin{aligned}
r'_0&:=0 \
r'_1&:=r_1-r_0 & k'_1&:=k_1+r_0\
&vdots & &vdots\
r'_ell&:=r_ell-r_0 & k'_ell&:=k_ell+r_0
end{aligned}
$$
so that $n':=sum_{i=1}^ell k'_i+sum_{i=0}^ell r'_i=n-r_0$, and rewriting the identity by replacing original parameters with primed parameters.

We can prove the equality of
$$binom{n-1}{m-1}binom{n}{m+1}binom{n+1}{m}=binom{n}{m-1}binom{n-1}{m}binom{n+1}{m+1}$$ by counting lattice paths. In order to do so, we consider paths from $(0,0)$ to $(X,Y)$ with certain properties corresponding to the LHS of the equation and paths from $(0,0)$ to $(X,Y)$ corresponding to the RHS and show that there is a $1$-$1$ correspondence due to the symmetry between these.

To see the symmetry easier, we rewrite the equation using multinomial coefficients and exchange variables. We get

$$binom{n-1}{m-1,n-m}binom{n}{m+1,n-m-1}binom{n+1}{m,n-m+1}=binom{n}{m-1,n-m+1}binom{n-1}{m,n-m-1}binom{n+1}{m+1,n-m}$$
Using the substitution $y=n-m,x=m$ with $x+y=n$ gives

$$binom{x+y-1}{x-1,y}binom{x+y}{x+1,y-1}binom{x+y+1}{x,y+1}=binom{x+y-1}{x,y-1}binom{x+y}{x-1,y+1}binom{x+y+1}{x+1,y}$$

The factors of the RHS are rearranged by increasing length of paths corresponding to the LHS.

Now we analyse the LHS: The leftmost factor
$$binom{x+y-1}{x-1,y}$$
is the number of paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$, the next one is the number of paths of length $x+y$ from $(0,0)$ to $(x+1,y-1)$ and the third one is the number of paths of length $x+y+1$ from $(0,0)$ to $(x,y+1)$.

Now we concatenate these paths, so that the endpoint of the previous part is the starting point of the next one. So, the first part consists of all paths of length $x+y-1$ from $(0,0)$ to $(x-1,y)$. The second part consists of all paths of length $x+y$ starting in $(x-1,y)$ and ending in $(2x,2y-1)$. The third part consists of all paths of length $x+y+1$ starting in $(2x,2y-1)$ and ending in $(3x,3y)$.

To formulate it simpler: The LHS gives the number of all paths of length $3x+3y$ from $(0,0)$ to $(3x,3y)$ going through $(x-1,y)$ and $(2x,2y-1)$.

$$LHS: (0,0)longrightarrow(x-1,y)longrightarrow(2x,2y-1)longrightarrow(3x,3y)$$

The RHS is now the symmetric pendant to the LHS. It shares the same properties and the same arguments hold. Therefore, the RHS gives the number of all paths of length $3x+3y$, starting from $(0,0)$ to $(3x,3y)$ and passing through $(x,y-1)$ and $(2x-1,2y)$.

$$RHS: (0,0)longrightarrow(x,y-1)longrightarrow(2x-1,2y)longrightarrow(3x,3y)$$

Since the passing points of the paths from LHS and RHS are symmetric with respect to the line $x=y$ and start point and end point are on this diagonal the number of paths is the same, showing that RHS and LHS are equal.

Note: Some generalisations which are adressed by Will Orrick can presumably also be shown using the symmetries of corresponding paths. :-)

Added 2014-03-19: Attention - This proof is not correct. The reasoning is only valid for the special case $x=y$. In case of $xne y$ an explicit description of a bijection between the paths of LHS and RHS is missing (see comments below).

Added 2014-03-21: Outline for a proof. Here is an outline how a bijection between the paths of the LHS and RHS for the general case including $x ne y$ could be created.

The plan is to show that all paths of the LHS can be mapped to a path from RHS and vice versa.

A geometrical representation of all paths of LHS, resp. RHS is given by a graph consisting of three rectangular grids having a vertex in common.

More precisely, all paths of LHS $L$ are within three rectangular grids $L=L_1L_2L_3$ with lower left and upper right points: $L_1: (0,0) rightarrow (x-1,y)$, $L_2: (x-1,y) rightarrow (2x,2y-1)$, and $L_3: (2x,2y-1) rightarrow (3x,3y)$. All paths start in $(0,0)$, pass through the vertices $(x-1,y)$ and $(2x,2y-1)$ and end in $(3x,3y)$.

Since we cannot completely cover the RHS rectangles with the LHS rectangles we add an additional step, which preserves bijection and is therefore admissible.

An admissible action is to perform one or more cyclic shifts on a path. So, a path $P=(P_1P_2)$ becomes $(P_2P_1)$ after a cyclic shift right of $length(P_2)$. This implies that we can extend the LHS grid $L=L_1L_2L_3$ by placing a copy of $L$ to the right and also to the left, symbolically: $LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$.

We are now free to cover parts from RHS $R=R_1R_2R_3$ with parts of $LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$ and identify pathes this way. We may also use different coverings by moving $LLL$ in $x$- and $y$-direction.

Each covering identifies all paths for which the following holds: They are completely within $R$ and $LLL$, they have length $3x+3y$ and whenever the path crosses rectangular regions $L_iL_j, L_iR_j, R_iL_j$ or $R_iR_j$, the path has to pass through the corresponding vertex joining these regions.

Since the rectangles in LHS and RHS differ at most by $2$ in $x$- and $y$- direction, a few coverings should be sufficient to cover all paths of RHS by these transformed copies of LHS.

In the same way LHS should be covered by transformed copies of RHS. Maybe some special cases ($x=1,y=1$) have to be considered separately.

This is not an answer, but rather, an explanation of the problems with the top-voted (as of 28 September 2018) answer (by Mitch). Although comments explaining the issues have been in place for many years, the answer has not been corrected or deleted, and continues to accumulate up-votes (two within the last couple of months), which leads me to believe that a more visible and detailed explanation is needed. I would also take this opportunity to urge readers to up-vote Markus Scheuer's answer, which is the only answer posted to date that provides a proof that is both correct and combinatorial.

The simplest kind of combinatorial proof counts a finite set in two different ways, leading to an equality between two counting formulas. A more complicated kind of combinatorial proof counts two different sets and then does the additional step of establishing a bijection between the two sets. The bijection shows that the two sets have the same size. Once again, an equality of two counting formulas follows. The first kind of proof can be thought of as a special case of the second kind in which the identity map serves as the bijection.

Mitch's answer claims to provide the former kind of proof, that is, to count the same set in two different ways, but, in fact, does not do this. It correctly interprets the two sides as enumeration formulas, but these enumeration formulas are for different sets, not the same set. To prove the equality, one would have to show that the sets have the same size, but the answer does not attempt to do this. The answer contains the phrases "This corresponds one-to-one with the RHS because the things counted by the LHS can be counted in a different way by the RHS" and "Another way to count this situation is...", but this is either wrong—the formulas count manifestly different things—or incoherent—what does it mean to count a situation?

Detailed explanation: One way of interpreting Mitch's argument is that both sides of the identity count sets of ordered triples of subsets taken from sets of specified sizes. The problem is that the two sides do not count the same set of ordered triples of subsets, but rather, two different sets of ordered triples of subsets. And, more importantly, no bijection is established between the two sets of ordered triples. To make this concrete, look at the hexagon surrounding the $2$ in the third row of the triangle. This corresponds to $n=2$, $m=1$, and the identity,
$$
binom{n-1}{m-1}binom{n}{m+1}binom{n+1}{m}=binom{n+1}{m+1}binom{n-1}{m}binom{n}{m-1},
$$
becomes
$$
binom{1}{0}binom{2}{2}binom{3}{1}=binom{3}{2}binom{1}{1}binom{2}{0}.
$$
(If you compare with Mitch's formulation, you will see that I have reordered the factors on the right to make them coincide with the order in which the sets in Mitch's prescription below get used in his argument.) Now Mitch observes that the formula on the left counts ways of forming an ordered triple of subsets by drawing no elements from the first set (of size $1$), two elements from the second set (of size $2$), and one element from the third set (of size $3$). Mitch then says to remove one element from the second set and one element from the third set, and to place these elements into the first set. The right side counts ways of forming an ordered triple of subsets by drawing two elements from this new first set, one element from this new second set, and no elements from this new third set.

If we somehow knew that the number of ways of forming ordered triples of subsets of the original three sets equalled the number of ways of forming ordered triples of subsets of the three new sets, then we would have a proof. The numbers of ordered triples on the two sides are, in fact, equal---the identity is true---but the question is how to demonstrate this.

To understand what's going on, let's look what the ordered triples on each side are in our concrete example. For the left side, let the first set be ${R}$, the second set ${G_1,G_2}$, and the third set ${B_1,B_2,B_3}$. The left side of the identity is computed to be $3$, and there are, indeed, three ordered triples of subsets:
$$
begin{aligned}
&({},{G_1,G_2},{B_1})\
&({},{G_1,G_2},{B_2})\
&({},{G_1,G_2},{B_3}).
end{aligned}
$$
Following Mitch's prescription for the right side, an element is removed from each of sets $2$ and $3$, say elements $G_1$ and $B_1$, and these elements are placed in set $1$, giving sets ${R,G_1,B_1}$, ${G_2}$, ${B_2,B_3}$. The right side of the identity also equals $3$, and there are, again, three ordered triples of subsets:
$$
begin{aligned}
&({G_1,B_1},{G_2},{})\
&({R,B_1},{G_2},{})\
&({R,G_1},{G_2},{}).
end{aligned}
$$

Clearly we don't expect the same ordered triples on the two sides since we've moved elements around. I surmise that the expectation in Mitch's answer was that the content of the triples, that is, the union of the three subsets composing the triple, would match up on the two sides. But the example shows that this doesn't happen either. Thinking of $R$ as a red object, $G_i$ as green objects, and $B_j$ as blue objects, we have a fixed color composition (no red, two greens, one blue) for all of the triples on the left, but not for the triples on the right. Of the triples on the right, only the triple $({G_1,B_1},{G_2},{})$ has the same content as a triple on the left.

To complete a proof along these lines, some rule would have to be formulated for matching up triples on the two sides, and it would have to be proved that this rule works for arbitrary $n$ and $m$. This has not been done. In fact, I don't believe that the proof can be patched up, for the following reason: nothing in the logic of the argument seems to rely on only one element being removed from each of the second and third sets and placed in the first set. Why not two elements from each, or one element from the second and two elements from the third, or some other combination of numbers from each? But if that is right, we should get many additional identities, namely
$$
binom{n-1}{m-1}binom{n}{m+1}binom{n+1}{m}=binom{n-1+k+ell}{m-1+k+ell}binom{n-k}{m+1-k}binom{n+1-ell}{m-ell},
$$
for arbitrary $k$ and $ell$. There is, however, no such general identity, as one can check by plugging in numbers. For example, let $n=4$, $m=3$, $k=ell=2$. Then
$$
binom{n-1}{m-1}binom{n}{m+1}binom{n+1}{m}=binom{3}{2}binom{4}{4}binom{5}{3}=30,
$$
while
$$
binom{n-1+k+ell}{m-1+k+ell}binom{n-k}{m+1-k}binom{n+1-ell}{m-ell}=binom{7}{6}binom{2}{2}binom{3}{1}=21.
$$
On the other hand, $k=ell=1$ does work:
$$
binom{5}{4}binom{3}{3}binom{4}{2}=30.
$$
Generalizations of the identity that actually hold are given in the cited article, as I note in my other answer. These generalizations do contain additional parameters, but they enter in a different way than do the $k$ and $ell$ in the formula above. And understanding the role of these additional parameters actually gives insight into what makes the identity tick.

A TV channel will broadcast six multi-part TV dramas which have the following numbers of parts:

• A: $m-1$ parts


• B: $n-m$ parts


• C: $m+1$ parts


• D: $n-m-1$ parts


• E: $m$ parts


• F: $n-m+1$ parts

The $3n$ time-slots when they will be broadcast are on $n-1$ Mondays, $n$ Wednesdays and $n+1$ Fridays. There are two possible schedules, which are as follows:

Schedule 1:

• A and B on Mondays


• C and D on Wednesdays


• E and F on Fridays

Schedule 2:

• D and E on Mondays


• A and F on Wednesdays


• B and C on Fridays

(I have for the most part taken the 6 terms in the order Mitch put them in his equation, but have swapped his RHS's first two terms so as to make the RHS's numerator-sequence match the LHS's.)

The parts of each drama must be broadcast in their correct order. However, the parts of different dramas may be interleaved at will.

Let $S_i$ be the set of broadcast-orders that fit Schedule $i$. Mitch's LHS is $|S_1|$. His RHS is $|S_2|$.

Choose an order that fits Schedule 1. This determines the order in which the $n-1$ D- and E-parts (collectively) are broadcast. This is a valid order for Schedule 2's Monday time-slots. Similarly for Schedule 2's Wednesday time-slots, and for its Friday time-slots. This thus determines a unique order that fits Schedule 2.

A similar argument, with the schedules swapped, also applies. Thus there is a bijection between $S_1$ and $S_2$. Thus $|S_1|=|S_2|$ which proves the identity specified by Mitch.