Journal of Combinatorics

Volume 2 (2011)

Number 4

Two further generalizations of the Calkin–Wilf tree

Pages: 507 – 524



Toufik Mansour (Department of Mathematics, University of Haifa, Israel)

Mark Shattuck (Department of Mathematics, University of Tennessee, Knoxville, Tenn., U.S.A.)


In this paper, we consider two further analogues of the Calkin–Wilf tree and of the Calkin–Wilf sequence. We first consider ($p, q$)-versions of these whereby we show that a two-variable generalization of the latter is given, equivalently, in terms of a generalization of the former. In particular, we show that the sequence of ($p, q$)-generating functions counting the hyperbinary expansions of $n$ according to the total number of distinct powers used and the number of powers used twice arises as the sequence of numerators for the rational functions which label the vertices of our ($p, q$)-Calkin–Wilf tree. We also define a $k$-dimensional $q$-generalization of the Calkin–Wilf tree and of the Calkin–Wilf sequence. Having defined the n-th term of the latter in terms of the generating function counting the hyper $k$-expansions of $n$ according to the number of powers that are used exactly $k$ times, we show that it is given equivalently in terms of the former.


Calkin–Wilf tree, Calkin–Wilf sequence, hyperbinary expansion, q-analogue

2010 Mathematics Subject Classification

Primary 05A30. Secondary 05A15.

Full Text (PDF format)