Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

triangle

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.

share|improve this question
    
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
    
About the BOUNTY: Mitch's answer provides a combinatorial interpretation of each side of the identity, showing that each side counts a certain collection of sets. His answer does not, however, show these two collections to be equinumerous, and therefore is NOT A PROOF. His answer asserts that the two collections are, in fact, the same, which would immediately establish that they are equinumerous, but this assertion is INCORRECT, as demonstrated in the comments. I am offering the bounty in hopes that someone will find a bijection between the two collections. –  Will Orrick Mar 16 at 14:43
add comment

3 Answers 3

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.

share|improve this answer
1  
@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
3  
@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
1  
@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
1  
@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
1  
… $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
show 4 more comments

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

share|improve this answer
    
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
add comment

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 pathes from $(0,0)$ to $(X,Y)$ with certain properties corresponding to the LHS of the equation and pathes 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 pathes corresponding to the LHS.

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

Now we concatenate these pathes, so that the endpoint of the previous part is the starting point of the next one. So, the first part consists of all pathes of length $x+y-1$ from $(0,0)$ to $(x-1,y)$. The second part consists of all pathes of length $x+y$ starting in $(x-1,y)$ and ending in $(2x,2y-1)$. The third part consists of all pathes 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 pathes of length $3x+3y$ from $(0,0)$ to $(3x,3y)$ passing 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 pathes 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 pathes from LHS and RHS are symmetric with respect to the line $x=y$ and starting point and endpoint are on this diagonal the number of pathes 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 pathes. :-)

Added 2014-03-19: Attention - This proof is not correct. The reasoning is only valid for the special case $x=y$. In case of $x\ne y$ an explicit description of a bijection between the pathes 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 pathes of the LHS and RHS for the general case including $x \ne y$ could be created. I will try to provide a proof during the weekend.

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

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

More precisely, all pathes 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 pathes 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 pathes 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 pathes 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.

share|improve this answer
    
Thank you for this wonderful answer. –  Will Orrick Mar 17 at 1:56
    
Thanks for your friendly comment. It was fun to work on this problem :-) –  Markus Scheuer Mar 17 at 7:23
    
In going through the details of your solution, I am only able to see how to make things work when $x=y.$ In that case, mirror symmetry about the line $y=x$ maps the LHS paths to the RHS paths. This takes care of the particular case I asked about, $n=2,$ $m=1,$ since then $x=y=1.$ In general, it takes care of $n=2m.$ But what about $x\ne y?$ In that case, the endpoint is not on the line of symmetry, so it wouldn't seem that things could work the same way. –  Will Orrick Mar 17 at 19:13
    
Oh, Will! You are right and I'm wrong! The symmetry is not a valid argument for the general case. A bijection between the pathes of LHS and RHS for the general case seems now to be a little bit more challenging ... I will think about it ... –  Markus Scheuer Mar 17 at 22:08
    
@Will: I think I found a proper way to create a bijection for the general case. I've to work it out, ... check it twice :-) ... and will post it within the next few days. Regards, Markus –  Markus Scheuer Mar 19 at 9:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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