14 March 2010

The Calkin-Wilf shirt

You can actually buy a shirt with the Calkin-Wilf tree on it. I probably should buy it, if only so I can wear it when I inevitably give a talk on this subject again, either as a stand-alone talk (I've done it twice) or when I teach it in a class.

This is an infinite binary tree of rational numbers. It has 1/1 at the root, and the children of r/s are r/(r+s) and (r+s)/s. It turns out that this tree contains every positive rational number exactly once, giving an explicit enumeration of the rational numbers.

Also -- and this is what's really surprising to me -- let f(n) be the number of ways to write n as a sum of powers of 2, where no power of 2 can be used more than twice. Then (f(0), f(1), f(2), ...) = (1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,...). The sequence of numbers f(n)/f(n+1) are the rational numbers in that tree, in the order which they appear if you traverse each level from left to right.

I learned about the shirt from this mathoverflow thread, where Richard Stanley gives the theorem of the previous paragraph as an example of a theorem with an "unexpected conclusion".

See the original paper by Calkin and Wilf. I've mentioned it before here and here. I think I first heard of this paper from Brent Yorgey's series of posts expanding upon the paper, or perhaps from Mark Dominus' blog. (Somewhat coincidentally, Yorgey and Dominus both live in Philadelphia. I claim this is coincidence, even though Wilf is at Penn, because I don't think either of them heard about the paper from Wilf.)

And can anything nice be said about the number of ways to write n as a sum of powers of 3, where no power of 3 can be used more than three times?


Jeffrey Shallit said...

It's the Stern-Brocot tree in disguise.

Mark Dominus said...

I heard about it from Yorgey's blog article, but I think he had not yet moved to Philadelphia then.

So yes, it was a coincidence.

Have you seen Wilf's appalling paper about the Coupon Collector problem?

Brent said...

Oh snap. I'm going to have to get one of those shirts.

Jeffrey: is it? What's the disguise?

Zander said...

Here's something similar I can say about the number of ways to write n as a sum of powers of 3, where no power of 3 can be used more than three times. It's A054390, and satisfies g(3n)=g(n-1)+g(n) and g(3n+1)=g(3n+2)=g(n).
Let T be a tree in which each node has 3 children, the root is numbered 1 and each node's children are ordered Left, Center, Right (L,C,R) and numbered 3n-1, 3n and 3n+1 respectively, and we associate with node number n the ordered pair (g(n-1),g(n)) and the rational number g(n-1)/g(n). Then if g(n-1)=r and g(n)=s, then node n has r/s and from the recurrence for g(n) the children L,C,R have r/r, r/(r+s) and (r+s)/s respectively. The C and R children of the node have the same relation to the parent as in the Calkin-Wilf tree, so if we take the subtree S of nodes for which the path from the root passes through only C and R children, it is exactly the C-W tree. The nodes of S are the nodes with numbers that have base-3 representations containing no 2s, and if we read them as binary numbers then it's also the natural numbering of nodes in the C-W tree.
Any L child has (r,r), so the subtree U that has L at the root and contains all of its descendants is a scaled copy of T in the sense that, for a node in T that has the ordered pair (a,b), the corresponding node in U has (r*a,r*b) and so both are associated with the same rational number.

Unknown said...

If you carry out Euclid's algorithm slowly, you get a sequence of "right" and "left" steps. If you write the steps in one order, you get the Calkin-Wilf tree. If you reverse the order of the steps, you get the Stern-Brocot tree. For example, the fraction in position 010011 in one is in position 110010 in the other, where the length of the string tells you which row you are in.

Since each row of the Stern-Brocot tree is increasing, you can also sort a row of the Calkin-Wilf tree to get the corresponding row of the Stern-Brocot tree.

The Stern-Brocot tree doesn't have the property that the denominator of one fraction is the numerator of the next.

Douglas Zare