I came across a curious connection between continued fractions and combinatorics on arxiv. It'll take some setup. Let's see how short I can make this...

A "snake graph" is either a "tile" (consisting of 4 vertices and 4 edges) or is built from a snake graph by adding a tile (consisting of 2 new vertices and 3 new edges) above, or to the right of the top right tile in a snake graph. The picture shows an example.

Call adding a tile above a "zig" and a tile to the right a "zag". Think of the first tile as a zig. Then the graph in the picture is constructed from a sequence (zig, zig, zig, zag, zig, zig, zag, zag, zag, zig).

Given a sequence made from two letters (say A and B) you can "compress" it using run length encoding, ie. by listing the length of runs of one letter, starting with the number of A's. Eg. ABBAAABAB becomes (1,2,3,1,1,1).

You can also anti-run length encode it. List the lengths of the anti-runs, i.e. the stretches of alternating letters. So ABBAAABAB, made of anti-runs AB-BA-A-ABAB, becomes (2,2,1,4).

We can anti-run encode the zigs and zags in a snake graph. The pictured graph becomes (1, 1, 3, 5).

Given a sequence a=(a1, ..., an) of integers greater than 0 and with the last greater than 1, we can read it as the anti-run length encoding of zigs and zags and build the corresponding snake graph, G(a).

These sequences also define continued fractions via [a] = [a1, a2, ..., an] = f(a1+1/(a2+1/(...1/an))).

A perfect matching of a graph is a subset of its edges where every vertex in the graph touches precisely one edge in the subset. If an edge between two people expresses compatibility between them, a perfect matching is a way of pairing everyone off as compatible couples. Let m(G) be the number of perfect matchings of G.

Now comes the theorem:

[a1, a2, ..., an] = m(G(a1, a2, ..., an-1))/m(G(a2, a3, ..., an-1)).

In addition, the numerator and denominator are coprime so no cancellation is possible.

I wrote some code to test this theorem, though it wasn't intended to be particularly readable:

https://gist.github.com/anonymous/1a18b3b7f5a8e1fac76e4b5dba281c1bI got this result from a paper on cluster algebras, whatever they are:

http://arxiv.org/abs/1608.06568 My notation might not follow the paper exactly.

BTW It's not hard to prove using elementary methods. You can almost read off a proof from my code.

And I probably made at least one mistake above...