![]() | A fact from Calkin–Wilf tree appeared on Wikipedia's
Main Page in the
Did you know column on 12 May 2009 (
check views). The text of the entry was as follows:
| ![]() |
![]() | This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
aWhat about the FAREY Tree? This predates Calkin-wilf by decades, and includes the essential ideas. —Preceding unsigned comment added by 85.61.225.8 ( talk) 23:25, 9 May 2009 (UTC)
In Aigner and Ziegler, Newman's formula for the next rational after q in the CW sequence is given as
where {q} stands for the fractional part of q. I very strongly dislike the {q} notation (that should be reserved for singleton sets), and would prefer to write this as
However, "mod 1" is likely confusing to people who have only seen modular notation used for integers. A trivial rearrangement avoids the mess altogether:
which is how I wrote it in the article. Now, an anonymous editor insists on changing it to the exact form written in Aigner and Ziegler, and I've changed it back twice. Rather than continuing to edit war over this, I'd appreciate opinions from other math editors on the subject so we can build a consensus on the proper way to treat this equation (and maybe also on the proper way of handling "fractional part" notation in future). — David Eppstein ( talk) 16:22, 18 May 2009 (UTC)
The CW tree use the same structure like the Mandelbrot Tree fractal: [2] —Preceding unsigned comment added by Bocutadriansebastian ( talk • contribs) 19:57, 22 February 2010 (UTC)
Personally, I think the first picture should be a typical binary tree since that's the more familiar shape, and maybe have a second image of the H-tree underneath. Loadedsalt ( talk) 00:38, 21 October 2012 (UTC)
The section Stern's diatomic sequence says "The nth value in the sequence is the value fusc(n) of the fusc function". Only the first value in the sequence is 0, and only fusc(0) = 0. So shouldn't the article say "The (n + 1)th value in the sequence is the value fusc(n) of the fusc function"? Of some of the integer sequence articles that I checked, the article Catalan number seems to have the same error. The lede of Integer sequence implies that a sequence begins with the 1st term. Olli Niemitalo ( talk) 09:49, 29 April 2015 (UTC)
I propose to exchange the first three paragraphs in Definition and structure with the following (please notice I am not a native English speaker). The proofs are mine.
The Calkin-Wilf tree is an infinite binary tree in which each vertex is associated with a positive rational number expressed as an irreducible fraction ; in particular, the number is associated with the root vertex. Each vertex has a left child whose value is and a right child whose value is .
Observation 1: Each vertex has a left child whose value is less than 1, since . Similarly, each vertex has a child on the right whose value is greater than 1.
Observation 2: The sum of the numerator and denominator of the first child is , while that of the second child is ; in both cases the sum is greater than that of the parent . It follows that by going down the tree, a strictly increasing sequence of sums is always obtained. On the contrary, going up the tree always results in a strictly decreasing sequence of sums.
The parent of any rational number can be determined after expressing the number as an irreducible fraction , i.e. such that the greatest common divisor of and is 1. If , the parent of is ; if , the parent of is . Therefore, the parent is a fraction whose sum of numerator and denominator is either or , and in both cases it is less than , which is the sum corresponding to the child fraction . It follows that a repeated reduction of this type must sooner or later reach the irreducible fraction with minimum sum, that is, the number . This is an informal proof that every rational number appears at least once as the vertex of the tree.
Furthermore, the parent formula provides for each step a unique sum value which is lower than the previous one, therefore, given any rational number, the sequence of sums to go up from the associated vertex to the root is unique and strictly decreasing (as already observed above). Assume there are two distinct vertices with the same rational number. Due to the structure of tree graphs, going up the tree from each one would sooner or later arrive at the same vertex. Since the sequence of sums is strictly decreasing, the number of steps taken to reach this vertex from each of the two starting vertices must be the same, otherwise we would have two distinct sum values ​​for this vertex. In other words, the two sequences of sums, as well as being equal, are also synchronized. It follows that the two children of the common vertex (which correspond to the previous step of the sequences) have the same sum value, which is in contradiction with the definition of the tree. The conclusion is that no two vertices with the same rational number can exist, that is, a certain rational number can appear at most once in the tree. Overall, therefore, each rational number appears exactly once in the tree in the form of an irreducible fraction. Colemarc ( talk) 17:02, 26 August 2022 (UTC)
![]() | A fact from Calkin–Wilf tree appeared on Wikipedia's
Main Page in the
Did you know column on 12 May 2009 (
check views). The text of the entry was as follows:
| ![]() |
![]() | This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
aWhat about the FAREY Tree? This predates Calkin-wilf by decades, and includes the essential ideas. —Preceding unsigned comment added by 85.61.225.8 ( talk) 23:25, 9 May 2009 (UTC)
In Aigner and Ziegler, Newman's formula for the next rational after q in the CW sequence is given as
where {q} stands for the fractional part of q. I very strongly dislike the {q} notation (that should be reserved for singleton sets), and would prefer to write this as
However, "mod 1" is likely confusing to people who have only seen modular notation used for integers. A trivial rearrangement avoids the mess altogether:
which is how I wrote it in the article. Now, an anonymous editor insists on changing it to the exact form written in Aigner and Ziegler, and I've changed it back twice. Rather than continuing to edit war over this, I'd appreciate opinions from other math editors on the subject so we can build a consensus on the proper way to treat this equation (and maybe also on the proper way of handling "fractional part" notation in future). — David Eppstein ( talk) 16:22, 18 May 2009 (UTC)
The CW tree use the same structure like the Mandelbrot Tree fractal: [2] —Preceding unsigned comment added by Bocutadriansebastian ( talk • contribs) 19:57, 22 February 2010 (UTC)
Personally, I think the first picture should be a typical binary tree since that's the more familiar shape, and maybe have a second image of the H-tree underneath. Loadedsalt ( talk) 00:38, 21 October 2012 (UTC)
The section Stern's diatomic sequence says "The nth value in the sequence is the value fusc(n) of the fusc function". Only the first value in the sequence is 0, and only fusc(0) = 0. So shouldn't the article say "The (n + 1)th value in the sequence is the value fusc(n) of the fusc function"? Of some of the integer sequence articles that I checked, the article Catalan number seems to have the same error. The lede of Integer sequence implies that a sequence begins with the 1st term. Olli Niemitalo ( talk) 09:49, 29 April 2015 (UTC)
I propose to exchange the first three paragraphs in Definition and structure with the following (please notice I am not a native English speaker). The proofs are mine.
The Calkin-Wilf tree is an infinite binary tree in which each vertex is associated with a positive rational number expressed as an irreducible fraction ; in particular, the number is associated with the root vertex. Each vertex has a left child whose value is and a right child whose value is .
Observation 1: Each vertex has a left child whose value is less than 1, since . Similarly, each vertex has a child on the right whose value is greater than 1.
Observation 2: The sum of the numerator and denominator of the first child is , while that of the second child is ; in both cases the sum is greater than that of the parent . It follows that by going down the tree, a strictly increasing sequence of sums is always obtained. On the contrary, going up the tree always results in a strictly decreasing sequence of sums.
The parent of any rational number can be determined after expressing the number as an irreducible fraction , i.e. such that the greatest common divisor of and is 1. If , the parent of is ; if , the parent of is . Therefore, the parent is a fraction whose sum of numerator and denominator is either or , and in both cases it is less than , which is the sum corresponding to the child fraction . It follows that a repeated reduction of this type must sooner or later reach the irreducible fraction with minimum sum, that is, the number . This is an informal proof that every rational number appears at least once as the vertex of the tree.
Furthermore, the parent formula provides for each step a unique sum value which is lower than the previous one, therefore, given any rational number, the sequence of sums to go up from the associated vertex to the root is unique and strictly decreasing (as already observed above). Assume there are two distinct vertices with the same rational number. Due to the structure of tree graphs, going up the tree from each one would sooner or later arrive at the same vertex. Since the sequence of sums is strictly decreasing, the number of steps taken to reach this vertex from each of the two starting vertices must be the same, otherwise we would have two distinct sum values ​​for this vertex. In other words, the two sequences of sums, as well as being equal, are also synchronized. It follows that the two children of the common vertex (which correspond to the previous step of the sequences) have the same sum value, which is in contradiction with the definition of the tree. The conclusion is that no two vertices with the same rational number can exist, that is, a certain rational number can appear at most once in the tree. Overall, therefore, each rational number appears exactly once in the tree in the form of an irreducible fraction. Colemarc ( talk) 17:02, 26 August 2022 (UTC)