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.
Subscribe to:
Post Comments (Atom)
5 comments:
s/depth/breadth/
Thanks. I thought "breadth" but somehow the wrong word made it out...
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.
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.
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.
Post a Comment