There are several mathematical heuristics (it’s difficult to call them proofs), which are non-rigorous in the best of cases and sometimes seemingly insane. For example, Euler’s ‘proof’ that the sum of the reciprocals of the primes diverges at an asymptotic rate of 
He proceeded to conclude the rate of divergence of the series. It transpires that whilst the proof was non-rigorous, one can easily repair it, in this case by replacing the infinite summations with partial sums and taking the limit. It’s very messy, though, but still possible (I recall doing this for an earlier cp4space post).
Seven trees in one
Whilst the Euler proof cheats slightly, it may appear to the untrained eye to be completely legitimate. We’ll now take a look at a more extreme example, which appears more like a mathematical joke than a proof, but again reaches a correct conclusion. Later, a rigorous general proof was published, stating ‘whenever this silly approach is employed, and certain constraints are obeyed, the result of this process is a true statement’.
The subject is Andreas Blass’ Seven Trees in One, which I would probably rank among my favourite mathematical papers. Essentially, the heuristic argument runs like this:
- Consider binary trees (with ordered leaves), and let each leaf be coloured with one of k colours. Here are a few examples of trees:
- There are
trees with n leaves, thus
if we colour the leaves. Hence, the total number of trees with coloured leaves is given by the series
, where the coefficients are Catalan numbers. This generating function has the closed form
.
- Evaluating this at
gives us the number of unlabelled trees,
. The astute observer will notice that this is a sixth root of unity, so
.
- Hence, there is an elegant bijection between trees and 7-tuples of trees.
Blass then provides such an elegant bijection in the paper. Here is a diagrammatic representation of the bijection, where the letters a, b, c, … represent arbitrary trees (including the ’empty tree’ consisting of a single leaf). To use this diagram, apply the first rule that applies to your 7-tuple.
Why does this work?
It is obvious that there were many non-sequiturs in the above derivation. Nevertheless, Blass provided a rigorous justification of this argument.
- A tree is either a leaf or an ordered pair of trees (the children of the root node). Hence, it makes sense to write T = 1 + T² (where T is the set of trees, multiplication corresponds to Cartesian product, ‘+’ gives the disjoint union of two sets, and ‘=’ means ‘there exists a natural bijection’).
- Now, if we were in a ring, we could rearrange to give
and multiply by
to give the desired equality,
. The reason this fails is that we’re not in a ring, but a semiring (ring without negatives).
- Nevertheless, in a semiring we can still apply the formula T = 1 + T² to ultimately derive the desired statement. Dan Piponi created a video, where a penny can bifurcate into two pennies in adjacent locations (corresponding to bijecting from the set of trees to the disjoint union of the singleton set and the set of ordered pairs of trees). The reverse process can also happen (since bijections are, by their very nature, invertible):
[youtube=http://www.youtube.com/watch?v=vtCV7JOnlhc]
If we replace each of these steps with the elementary bijection, the whole thing gives the bijection from trees to 7-tuples of trees.
In pseudoproof of this bijection you probably forgot to put imaginary unit in value of T
I don’t understand your diagram of the bijection although I understand how to get the bijection and the penny game. Can you explain it with a little more detail?