# 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)$.

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.

-
The Hoggatt and Hansell article has now been brought online: page 1, page 2. I don't think, however, that it helps with your question. –  Will Orrick Jan 28 at 18:08

## This question has an open bounty worth +100 reputation from Will Orrick ending in 6 days.

The current answers do not contain enough detail.

My own answer isn't satisfactory as a bijective proof since it starts multiplying both sides by the same quantity, thereby changing the count. At the same time, I am still not seeing the bijection in Mitch's answer. I'd be very happy if someone could turn either of these arguments into a genuine bijection that I am able to follow. New answers welcome too.

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-1\atop m-1}\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.

-
@milcak: I added a paragraph stating more clearly the combinatorial part. I am not using the arithmetic of factorials in my proof, simply using the combinatorial interpretation of binomial coefficients as counting subsets and counting one situation in two different ways. –  Mitch Feb 7 '11 at 18:11
@milcak This proof is completely combinatorial: it combinatorially interprets the two sides of the equality you want to prove and then combinatorially establishes the equality. I don't see what more you want. –  Alex B. Feb 21 '11 at 5:20
@milcak: can you give an example of a proof of an identity involving just binomial coefficients that would be sufficient to be called 'combinatorial' by you? You may want to explain to what degree your example is 'pure' or avoids the use of 'how pascal's triangle is constructed'. (before dismissing my example, you should confirm that it does not use Pascal's identity) –  Mitch Feb 23 '11 at 3:20
@AlexB., Mitch : I'm somehow not yet able to see the bijection in this proof. Let's say that the set of size $n-1$ consists of red balls, the set of size $n$ consists of green balls, and the set of size $n+1$ consists of blue balls. On one side, we have selections of $m-1$ balls from a set $n-1$ red balls, $m+1$ balls from a set of $n$ green balls, and $m$ balls from a set of $n+1$ blue balls. On the other, we have selections of... –  Will Orrick Jan 20 at 21:41
… $m+1$ balls from a set containing $n-1$ red balls, one green ball, and one blue ball, $m$ balls from a set of $n-1$ green balls, and $m-1$ balls from a set of $n$ blue balls. The selections on the left all have $m-1$ red, $m+1$ green, and $m$ blue balls, but the selections on the right don't necessarily have this color composition. For instance, a selection on the right might instead have $m+1$ red balls, $m$ green balls, and $m-1$ blue balls. Or $m$ red balls, $m+1$ green balls, and $m-1$ blue balls. Or $m$ red balls, $m$ green balls, and $m$ blue balls. –  Will Orrick Jan 20 at 21:44

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

-
I haven't been ignoring you. I'm still thinking about all this. –  Mitch Jan 28 at 2:37
@Mitch: no worries. Thanks for thinking about it. –  Will Orrick Jan 28 at 18:01