07 May 2009

The Calkin-Wilf tree on Wikipedia

The Calkin-Wilf tree now has a Wikipedia page. This is an infinite binary tree with rational numbers at the nodes, such that it contains each rational number exactly once. In the sequence of rational numbers that one gets from breadth-first traversal of the tree,

1/1, 1/2,2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...

the denominator of each number is the numerator of the next; furthermore the sequence of denominators (or of numerators) actually counts something. Plus, there are some interesting pictures that come from plotting these sequences, and some interesting probabilistic properties (see arXiv:0801.0054 for some of the probabilistic stuff, although I actually just found it and haven't read it thoroughly) I've given a talk about this; one day I'll write down some version of it. This is one of my favorite mathematical objects.

It looks like we've got David Eppstein to thank for this. It was introduced in this article by Calkin and Wilf.

5 comments:

Anonymous said...

s/depth/breadth/

Michael Lugo said...

Thanks. I thought "breadth" but somehow the wrong word made it out...

Anonymous said...

Oh good, someone else who knows about this has seen the article. Do let me know if I've said something bogus or omitted something important, please.

Chris Wellons said...

Your post seemed so familiar until I remembered that I first heard of the Calkin and Wilf's Recounting the rationals about a year ago over at The Universe of Discourse, where he also linked to a 6-part blog series about it.

Nerdy Shirts Guy said...

The Calkin-Wilf tree has shown up in some problem sites, including Project Euler.

I like it so much that I designed a math shirt featuring the Calkin-Wilf tree.