A Combinatorial Proof of Dixon's Identity
Dixon's Identity states: $$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c} {a,b,c}$$
A bit of history: The case $a=b=c$ was proved by Dixon in 1891 using trigonometric integrals. He proved the general case 11 years later using other analytical methods. In 1916, MacMahon proved his master theorem which gives another short analytical proof for the identity.
Using the WZ-method, Zeilberger gave a short proof in 1990 (with the aid of his computer). In 2003, Victor Guo gave a short proof using polynomials.
But what really interests me are the combinatorial interpretations.
Zeilberger gives a proof using sign-reversing involutions in this lecture (starting from 39:30). Does it exist in some paper? I believe he credits it to Foata in this opinion.
-
In this monograph by Foata, there seems to be a combinatorial proof of Dixon's identity and other related identities (pages 37 to 40). I wasn't able to understand the part in pages 37-38, where the following is derived combinatorially: $$\binom{b+c}{c+k}\binom{c+a}{a+k}\binom{a+b}{b+k}=\sum_{n\ge |k|} \binom{a+b+c-n}{a-n,b-n,c-n,n+k,n-k}$$ Where both sides seem to count directed graphs with the following adjacency matrix: $$\begin{bmatrix} 0 & c+k & b-k \\ c-k & 0 & a+k\\ b+k & a-k & 0 \end{bmatrix}$$ The LHS counts it directly, and the RHS counts it by decomposing by using 5 basic cycles: $1\to 2 \to 1$ (appearing $a-n$ times), $1\to 3 \to 1$ ($b-n$ times), $2\to 3 \to 2$ ($c-n$ times), $1\to 2 \to 3 \to 1$ ($n+k$ times), $1\to 3 \to 2 \to 1$ ($n-k$ times). But I don't really understand how they actually count it.
Here's a picture of the relevant pages:
Is the paper "100 years of Dixon's identity" by James Ward (published in 1991 in the Irish Mathematical Society Bulletin") available online?
Here are some remarks on the identity proof related to your second question. Hopefully they will make you understand everything, feel free to ask more about this proof.
Remark 1 Brian Hopkins’ comment is half correct and half incorrect. It is indeed true that loops are forbidden (this is indicated by the “$i\neq j$” statement on the second line of p.37). On the other hand, multiple edges are definitely needed (and allowed) : otherwise, you could hardly multiply two cycles together and the whole proof would be nonsensical.
Remark 2 Your cycle is not a counterexample, as it can be decomposed as $[123][132]$ or $[132][123]$, depending on how you number your multiple edges. It is very important to remember that the multiple edges are NUMBERED, this is what allows us to make the product of cycles to be non-commutative (see the definition of the product on the middle of p.15).
Remark 3 The integers $a,b,c,n,k$ in formulas (1),(2),(3) on the bottom of page 37 are uniquely defined by $$ a=\varepsilon_3+\frac{\varepsilon_4+\varepsilon_5}{2}, \ b=\varepsilon_2+\frac{\varepsilon_4+\varepsilon_5}{2}, \ c=\varepsilon_1+\frac{\varepsilon_4+\varepsilon_5}{2}, \ n=\frac{\varepsilon_4+\varepsilon_5}{2}, \ k=\frac{\varepsilon_4-\varepsilon_5}{2} $$
Remark 4 There is a typo in the formula for matrix $N$ on the top of p.38 : the $(3,2)$ coefficient should be $a+k$ (not $b-k$ as it is printed).