The Hexagonal Property of Pascal's Triangle - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:37:45Z http://mathoverflow.net/feeds/question/56138 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56138/the-hexagonal-property-of-pascals-triangle The Hexagonal Property of Pascal's Triangle milcak 2011-02-21T03:46:07Z 2011-02-21T06:49:10Z <p>Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that:</p> <ul> <li><p>the product of non-adjacent vertices is constant.</p></li> <li><p>the greatest common divisor of non-adjacent vertices is constant.</p></li> </ul> <p><a href="http://i.imgur.com/pChFw.png" rel="nofollow">Here</a> 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)$.</p> <p>There is a quick proof <a href="http://www.fq.math.ca/Scanned/12-1/gupta.pdf" rel="nofollow">here (pdf).</a> The original proof should be in <em>V. E. Hoggatt, Jr., &amp; W. Hansell. "The Hidden Hexagon Squares." The Fibonacci Quarterly 9(1971):120, 133.</em> but I cannot access it.</p> <p>I am, however, intereseted in a purely <em>combinatorial</em> 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?</p> <p><a href="http://math.stackexchange.com/questions/20749/the-hexagonal-property-of-pascals-triangle" rel="nofollow">I have asked this question on math.se</a>, I have not yet received a satisfactory anwser. (The anwser provided there, is <em>somewhat</em> combinatorial in spirit, but maybe <em>one level down,</em> 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.)</p> <p><strong>EDIT:</strong> 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.</p> <p>Thanks.</p> http://mathoverflow.net/questions/56138/the-hexagonal-property-of-pascals-triangle/56143#56143 Answer by Theo Johnson-Freyd for The Hexagonal Property of Pascal's Triangle Theo Johnson-Freyd 2011-02-21T05:36:45Z 2011-02-21T06:49:10Z <p><em>Update: I have dramatically improved my original proof, and left it below a horizontal rule.</em>_</p> <p>I will prove the following stronger result from <a href="http://www.fq.math.ca/Scanned/12-1/gupta.pdf" rel="nofollow">A.K. Gupta, Generalized hidden hexagon squares, Fibonacci Quarterly, 1974</a>: <code>$$\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}$$</code></p> <p><strong>Proof:</strong></p> <p>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$.</p> <p>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.</p> <p>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: <code>$$\binom{a+b}{b-p} \binom{a+b+q}{b} \binom{a+b+p}{b-q} = (p\leftrightarrow q)$$</code> with no conditions on the signs of any number (only that $a,b,p,q$ are all integers).</p> <p>Setting $n=a+b$, $m=b$, $r=p$, $s=-q$ (for example) gives the desired result.</p> <hr> <p><em>My earlier proof; some comments apply to it:</em></p> <p>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: <code>$$\binom{n}{m-r,s} = \binom{n}{m-r}\binom{n-(m-r)}{s} = \binom{n-s}{m-r} \binom{n}{s}$$</code> <code>$$\binom{n}{m,s} = \binom{n-s}{m} \binom{n}{s} = \binom{n}{m+s} \binom{m+s}{s}$$</code> <code>$$\binom{n+r}{m,s} = \binom{n+r}{m+s} \binom{m+s}{s} = \binom{n+r}{m} \binom{(n+r)-m}{s}$$</code> Multiplying these equations together and canceling like terms gives the desired equality.</p> <p>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$.</p> <p>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".</p> <p>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$.</p>