5
$\begingroup$

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.

Here is one such hexagon. As an example, 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, interested 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?

I have asked this question on math.se, I have not yet received a satisfactory anwser. (The anwser provided there, is somewhat combinatorial in spirit, but maybe one level down, from what I am looking for. It begins with "In symbols, the identity is..." and then only uses the in-or-out arguement to finish up. It would be perfect if someone shared a problem/application of this too.)

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.

$\endgroup$
12
  • 1
    $\begingroup$ Mitch's proof on math.se is purely combinatorial--what about that proof does not suffice? $\endgroup$ Feb 21, 2011 at 3:48
  • 1
    $\begingroup$ I'm not a user at math.se, so I'll leave my comments here. Mitch's proof is completely combinatorial, and I don't expect you will do better here. I think you were turned off by the opening sentence, because you thought Mitch was speaking down to you, but that's a mistaken interpretation: most mathematicians are very careful to state everything, even things that they assume the reader knows; this is all the more important on sites like MO and M.SE, because other people are invited to read the posts, and they may not know as much as you do but still learn from reading the answers. $\endgroup$ Feb 21, 2011 at 4:06
  • $\begingroup$ The proof starts by expressing the property in a formula. I find that none combinatorial right away. Furthermore, to establish the equality he uses the same arguement 3 times, namely, a variation on an in-or-out arguement. I do believe there is a more intrinsic justification of this property. I'm looking for something such as one triple in the hexagon counts ..., the other ..., without actually coming back to each binomial independently. $\endgroup$
    – milcak
    Feb 21, 2011 at 4:09
  • $\begingroup$ @milcak: The proof has to use the definition of the binomial coefficient somehow... $\endgroup$ Feb 21, 2011 at 4:10
  • $\begingroup$ @Theo No, I do not get turned off by such things - on these sites people do not know each others background, and so I understand why he posted that. However, his proof dissasambles the triads of the hexagons. I understand how you can see it is combinatorial, I just want something that uses the entire triad to count something, somehow. $\endgroup$
    – milcak
    Feb 21, 2011 at 4:12

1 Answer 1

6
$\begingroup$

Update: I have dramatically improved my original proof, and left it below a horizontal rule._

I will prove the following stronger result from A.K. Gupta, Generalized hidden hexagon squares, Fibonacci Quarterly, 1974: $$ \binom{n}{m-r} \binom{n-s}{m} \binom{n+r}{m+s} = \binom{n-s}{m-r} \binom{n}{m+s} \binom{n+r}{m} $$

Proof:

Consider the following problem: divide a set of size $3(a+b) + p + q$ into sets of size $a+p$, $a+q$, $b-p$, $b-q$, $b$, and $a+p+q$.

You can lump them as $(a+p)+(b-p)$, $(a+q)+(b)$, and $(a+p+q)+(b-q)$, whence the problem becomes into two parts: first divide the big set into sizes $a+b$, $a+b+q$, and $a+b+p$, and then do $\binom{a+b}{b-p} \binom{a+b+q}{b} \binom{a+b+p}{b-q}$ choices.

Alternately, you can switch the roles of $p$ and $q$ in the previous paragraph; either way you first divide the same big set into the same three pieces, but then how you divvy up the pieces looks different. Note that if all six of the small sets have nonnegative size, then so do the three big sets. So we have proven: $$ \binom{a+b}{b-p} \binom{a+b+q}{b} \binom{a+b+p}{b-q} = (p\leftrightarrow q) $$ with no conditions on the signs of any number (only that $a,b,p,q$ are all integers).

Setting $n=a+b$, $m=b$, $r=p$, $s=-q$ (for example) gives the desired result.


My earlier proof; some comments apply to it:

Let me write $\binom{a}{b,c}$ for the number of ways to choose two disjoint sets, of sizes $b,c$ respectively, from a set of size $a$. There are a few ways to do this: you could first pick $b$ of them, and then pick $c$ from the remaining, or you could pick $b+c$, and then decide how to divy them up, or... Thus, we have the following equalities: $$ \binom{n}{m-r,s} = \binom{n}{m-r}\binom{n-(m-r)}{s} = \binom{n-s}{m-r} \binom{n}{s} $$ $$ \binom{n}{m,s} = \binom{n-s}{m} \binom{n}{s} = \binom{n}{m+s} \binom{m+s}{s} $$ $$ \binom{n+r}{m,s} = \binom{n+r}{m+s} \binom{m+s}{s} = \binom{n+r}{m} \binom{(n+r)-m}{s} $$ Multiplying these equations together and canceling like terms gives the desired equality.

This does not provide a combinatorial interpretation when both sides are $0$ --- indeed, it applies only when all of $s$, $m$, $n-s$, and $n+r-m-s$ are nonnegative integers, as in other situations I had asked to divide by $0$.

I will not try to improve this, as you asked for a combinatorial proof, and I won't try to give combinatorial interpretation to "the number of ways to pick negatively many objects form a set with negative size".

In words, I start with sets of size $n$, $n$, and $n+r$, and remove a set of size $s$ from each, and then remove from what remains sets of size $m-r$, $m$, and $m$; I count the ways to do this in various ways, and notice one coincidence, that $n-(m-r) = (n+r) - m$.

$\endgroup$
2
  • $\begingroup$ One thing that's disappointing in my proof is the coincidence. Another is that it doesn't highlight the symmetry under $r \leftrightarrow -s$. There should be a similar formula with $s \leadsto -s$, and a good exercise is to give a similar proof of that formula. $\endgroup$ Feb 21, 2011 at 5:57
  • $\begingroup$ Yes that's true there is a nice symmetry under $r$ and $s$! Maybe my question should be "why do the triads behave so nicely?" Could you please give an insight into that? Or am I not thinking deeply enough about the anwsers already given to me?? $\endgroup$
    – milcak
    Feb 21, 2011 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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