The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that:

• the product of non-adjacent vertices is constant.

• the greatest common divisor of non-adjacent vertices is constant.

Below is one such hexagon. As an example, here we have that $4 \cdot 10 \cdot 15 = 6 \cdot 20 \cdot 5$, as well as $\gcd(4, 10, 15) = \gcd(6,20,5)$.

$$ 1 \\ 1 \qquad 1\\ 1\qquad 2\qquad 1\\ 1\qquad3\qquad3\qquad1\\ 1\qquad\mathbf{4}\qquad\mathbf{6}\qquad4\qquad1\\ 1\qquad\mathbf{5}\qquad10\qquad\mathbf{10}\qquad5\qquad1 \\ 1\qquad6\qquad\mathbf{15}\qquad\mathbf{20}\qquad15\qquad6\qquad1$$

There is a quick proof here (pdf). The original proof should be in V. E. Hoggatt, Jr., & W. Hansell. "The Hidden Hexagon Squares." The Fibonacci Quarterly 9(1971):120, 133. but I cannot access it.

I am, however, intereseted in a purely combinatorial proof. I do not know how to approach this at all: I cannot see what the non-adjacent vertices represent and/or I do not know how to remodel their meaning. Can anyone help?

EDIT: To specify my question more closely, what I am looking for is some natural bijection between the two sets of triads that create the hexagon.

Thanks.

In symbols, the identity is

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

The usual combinatorial interpretation of a binomial coefficient $\left({n\atop 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-1\atop (m+1)-1}\right)$ and $\left({(n+1)-1\atop 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},\qquad\qquad(*) $$ 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 $\ell\ge2$, let $k_1$, $k_2$, ..., $k_\ell$, $r_0<r_1<\ldots<r_\ell$ be integers such that $k_i+r_0\ge0$ for all $i\in\{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.