So, I have answer to the questions from my previous post! No need to ask MathOverflow. :) I'll have to go write this up as a page on my website later. (I mean, notionally it could be a short paper somewhere to the extent these observations are original, but that adds a bunch of work and when it comes to actual math papers I've got higher priorities than this! I just want something that I can cite when I go to update OEIS with this information, an webpage with quick proofs should suffice for that. :P )
OK, so, let's start with the big one: Why is the reading sequence of Beren's tree identical to A232560, the inverse permutation of A232559, the reading sequence of the double-or-increment tree? (Where only even numbers have the option to increment, to prevent redundancy.)
Well, before we answer that, let's make an observation about the shape of this second tree. Beren's tree is Fibonacci based in terms of content, but it's a binary tree in shape. While the double-or-increment tree is based on binary... but in shape, it's Fibonacci. The lengths of the rows are Fibonacci numbers, because it's doing the Fibonacci rabbit thing, where only even-valued nodes (adult rabbits) can have two children, with odd-valued nodes (juvenile rabbits) having only one.
So, we have a Fibonacci binary tree and a binary Fibonacci tree. Less strange now that they're inverse, isn't it?
OK, but that doesn't explain why they actually are. Consider especially -- these trees do have different shapes. If the trees had the same shape, then we could regard these two permutations not as being on the linearly-ordered natural numbers, but rather on the spots of the unlabeled tree of that shape, and show that the permutations were inverse that way, without having to ever involve ourselves with the whole "reading sequence" business. Since that is not the case, however, we can't take that approach, and we will have to involve the reading order at some point.
Anyway, before we go any further, let's subtract 1 from each number in both trees, so we'll now be dealing with permutations of the whole numbers {0, 1, 2, ...} rather than of the positive integers {1, 2, 3, ...}. We do this because, as mentioned, Beren's tree, when you subtract 1 from each number, becomes this dual-Zeckendorf tree.
So: On the one hand, we have our dual Zeckendorf tree. In this tree, 0 is the root (the empty string in dual Zeckendorf), taking the left child corresponds to appending 1 (to the dual-Zeckendorf representation), and taking the right child corresponds to appending 01.
What about our other tree? Well, if we don't subtract 1, then it's a tree of binary representations; 1 is the root; even numbers have two children, with the left child corresponding to changing the final 0 to a 1, and the right child corresponding to appending 0; and odd numbers have one child, corresponding to appending 0.
OK, but what if we do subtract 1? Well, then it's a tree of bijective binary representations! The doubling operation becomes double-and-increment. So now 0 (the empty string) is the root; it's odd numbers that have two children, with the left child meaning you change the final 1 to a 2, and the right child meaning you append a 1; and even numbers have only one child, corresponding to appending a 1.
In order to see that these trees have inverse reading permutations, I want to introduce two auxiliary trees. We have a Fibonacci binary tree and a binary Fibonacci tree, but for comaprison, I'm going to introduce a binary binary tree and a Fibonacci Fibonacci tree.
That is to say -- consider the binary tree that, when read across, simply yields 0, 1, 2, 3, etc. This, if we look at it in bijective binary, can be described as a tree with root 0 (the empty string), where the left child is append a 1, and the right child is append a 2.
We can do the same thing on the other side; we can take a tree as the same shape as our Fibonacci-shaped tree of bijective binary numbers, but one whose reading sequence is simply 0, 1, 2, 3, etc. This similarly has a natural interpretation in terms of dual Zeckendorf; left children mean append a zero, right (or only) children mean you append a 1. Only numbers that are a 1-child can have a 0-child. (The identity of these two descriptions of the tree might not be obvious, but it follows from the fact that to compare two numbers written in dual Zeckendorf, you just do so lexicographically.)
So: Let us consider the permutation that takes our binary binary tree (whose reading sequence is just the whole numbers) to our Fibonacci (dual-Zeckendorf) binary tree (which has the same shape). What does it do to the number at any given spot? Well, what you do to the number is, you write the number in bijective binary; then you change each 2 to a 10 while leaving each 1 as a 1; then you interpret the string as dual Zeckendorf. So that's our permutation one way.
Now, we consider the permutation that takes our Fibonacci Fibonacci tree (whose reading sequence is just the whole numbers) to our binary Fibonacci tree (which has the same shape). What does this do to the number at any given spot? Well, you write the number in bijective binary; then, starting with the empty string, you interpret each 1 as an "append 1" and each 0 as a "change the final 1 to a 2" (because a 0-child must have a parent that is a 1-child, this is well-defined); then you interpret the string as bijective binary. That's our permutation the other way.
And, well, those two operations are inverse to each other, so there you go! Where did we use the reading order? How did we deal with the fact that the two trees are different shapes? By setting up two auxiliary trees which, although they had different shapes from each other, had identical reading sequences. Basically we had a chain of four trees, FB-BB-FF-BF, where the pairs FB-BB and FF-BF have the same shape, while the pairs BB-FF have the same reading sequence.
Now, you may have noticed here that we used dual Zeckendorf and bijective binary, with roots starting from 0. But what if we had used ordinary Zeckendorf, with root starting from 1? Where the left child meant "append 0" and the right child meant "append 01"? Well, in that case, the same proof as above implies that our corresponding "inverse" tree would be a tree based on ordinary binary, with 1 as the root... a tree that is almost the same as our original double-or-increment tree, before we subtracted 1 from everything. The only difference? It'd be flipped left-to-right. That tree had the left child meaning "change the final 0 to a 1" (when there were two children) and the right child meaning "append a 0"; here it would be the other way around.
To summarize, here's a list of the (nontrivial) involved trees and the relations between them. Here, "B" stands for "binary", "Z" stands for "Zeckendorf", "D" stands for "dual Zeckendorf", and "J" stands for "bijective binary". The first letter describes the representation used to make the numbers in the tree, while the second letter represents the shape of the tree (note "J" is not a separate shape from "B"). And Beren's original tree I'm just going to label "TB" because uh I dunno. :P
List of involved trees, excluding trivial trees (those whose reading sequences are just consecutive whole numbers or positive integers):
TB: Beren's original tree. Has 1 as the root.
DB: Dual-Zeckendorf binary tree. Has 0 as the root.
BD: The original double-or-increment tree. Has 1 as the root.
JD: Double-and-increment-or-just-increment tree. Has 0 as the root.
BZ: Double-or-increment tree, but reversed. Has 1 as the root.
ZB: Zeckendorf binary tree. Has 1 as the root.
Relations among involved trees:
TB = DB + 1
BD = JD + 1
BD = flip(BZ)
TB and BD have inverse reading permutations (starting from 1).
DB and JD have inverse reading permutations (starting from 0).
ZB and BZ have inverse reading permutations (starting from 1).
Um, I realize that's likely a bit confusing, but I hope it clears things up somewhat? Here's a diagram:
(One would of course get more relations if one looked at reverse reading permutations, where you read each row right-to-left, but I don't see a need to discuss that... all that is implied from the above.)
Now you'll notice that nowhere above did I discuss bijective Zeckendorf, because, well, it doesn't seem to really fit into the above very well. But I do have something to say about it, that answers my other two questions from last time!
So, one of the things that's special about binary, that doesn't hold for higher bases, is the close relation between ordinary binary and bijective binary. Namely, for n≥1, the bijective binary for n-1, is the same as the binary for n, but with the leading 1 removed and with 1 added to each digit.
Bijective Zeckendorf was frustrating me because I expected there to be a similar relation, but I wasn't seeing one. Except, oops, it's actually really easy, not sure how I missed it! Namely, for n≥2, the bijective Zeckendorf for n-2, is the same as the Zeckendorf for n, but with the leading 10 removed and with 1 added to each digit. This immediately answers both of my questions about bijective Zeckendorf from the previous post! As in the case of binary, one can see this either by examining how sums of Fibonacci works, or by examining how counting works.
So, yay, all three questions answered! Now when I have some time I need to go make a webpage about this...
OK, so, let's start with the big one: Why is the reading sequence of Beren's tree identical to A232560, the inverse permutation of A232559, the reading sequence of the double-or-increment tree? (Where only even numbers have the option to increment, to prevent redundancy.)
Well, before we answer that, let's make an observation about the shape of this second tree. Beren's tree is Fibonacci based in terms of content, but it's a binary tree in shape. While the double-or-increment tree is based on binary... but in shape, it's Fibonacci. The lengths of the rows are Fibonacci numbers, because it's doing the Fibonacci rabbit thing, where only even-valued nodes (adult rabbits) can have two children, with odd-valued nodes (juvenile rabbits) having only one.
So, we have a Fibonacci binary tree and a binary Fibonacci tree. Less strange now that they're inverse, isn't it?
OK, but that doesn't explain why they actually are. Consider especially -- these trees do have different shapes. If the trees had the same shape, then we could regard these two permutations not as being on the linearly-ordered natural numbers, but rather on the spots of the unlabeled tree of that shape, and show that the permutations were inverse that way, without having to ever involve ourselves with the whole "reading sequence" business. Since that is not the case, however, we can't take that approach, and we will have to involve the reading order at some point.
Anyway, before we go any further, let's subtract 1 from each number in both trees, so we'll now be dealing with permutations of the whole numbers {0, 1, 2, ...} rather than of the positive integers {1, 2, 3, ...}. We do this because, as mentioned, Beren's tree, when you subtract 1 from each number, becomes this dual-Zeckendorf tree.
So: On the one hand, we have our dual Zeckendorf tree. In this tree, 0 is the root (the empty string in dual Zeckendorf), taking the left child corresponds to appending 1 (to the dual-Zeckendorf representation), and taking the right child corresponds to appending 01.
What about our other tree? Well, if we don't subtract 1, then it's a tree of binary representations; 1 is the root; even numbers have two children, with the left child corresponding to changing the final 0 to a 1, and the right child corresponding to appending 0; and odd numbers have one child, corresponding to appending 0.
OK, but what if we do subtract 1? Well, then it's a tree of bijective binary representations! The doubling operation becomes double-and-increment. So now 0 (the empty string) is the root; it's odd numbers that have two children, with the left child meaning you change the final 1 to a 2, and the right child meaning you append a 1; and even numbers have only one child, corresponding to appending a 1.
In order to see that these trees have inverse reading permutations, I want to introduce two auxiliary trees. We have a Fibonacci binary tree and a binary Fibonacci tree, but for comaprison, I'm going to introduce a binary binary tree and a Fibonacci Fibonacci tree.
That is to say -- consider the binary tree that, when read across, simply yields 0, 1, 2, 3, etc. This, if we look at it in bijective binary, can be described as a tree with root 0 (the empty string), where the left child is append a 1, and the right child is append a 2.
We can do the same thing on the other side; we can take a tree as the same shape as our Fibonacci-shaped tree of bijective binary numbers, but one whose reading sequence is simply 0, 1, 2, 3, etc. This similarly has a natural interpretation in terms of dual Zeckendorf; left children mean append a zero, right (or only) children mean you append a 1. Only numbers that are a 1-child can have a 0-child. (The identity of these two descriptions of the tree might not be obvious, but it follows from the fact that to compare two numbers written in dual Zeckendorf, you just do so lexicographically.)
So: Let us consider the permutation that takes our binary binary tree (whose reading sequence is just the whole numbers) to our Fibonacci (dual-Zeckendorf) binary tree (which has the same shape). What does it do to the number at any given spot? Well, what you do to the number is, you write the number in bijective binary; then you change each 2 to a 10 while leaving each 1 as a 1; then you interpret the string as dual Zeckendorf. So that's our permutation one way.
Now, we consider the permutation that takes our Fibonacci Fibonacci tree (whose reading sequence is just the whole numbers) to our binary Fibonacci tree (which has the same shape). What does this do to the number at any given spot? Well, you write the number in bijective binary; then, starting with the empty string, you interpret each 1 as an "append 1" and each 0 as a "change the final 1 to a 2" (because a 0-child must have a parent that is a 1-child, this is well-defined); then you interpret the string as bijective binary. That's our permutation the other way.
And, well, those two operations are inverse to each other, so there you go! Where did we use the reading order? How did we deal with the fact that the two trees are different shapes? By setting up two auxiliary trees which, although they had different shapes from each other, had identical reading sequences. Basically we had a chain of four trees, FB-BB-FF-BF, where the pairs FB-BB and FF-BF have the same shape, while the pairs BB-FF have the same reading sequence.
Now, you may have noticed here that we used dual Zeckendorf and bijective binary, with roots starting from 0. But what if we had used ordinary Zeckendorf, with root starting from 1? Where the left child meant "append 0" and the right child meant "append 01"? Well, in that case, the same proof as above implies that our corresponding "inverse" tree would be a tree based on ordinary binary, with 1 as the root... a tree that is almost the same as our original double-or-increment tree, before we subtracted 1 from everything. The only difference? It'd be flipped left-to-right. That tree had the left child meaning "change the final 0 to a 1" (when there were two children) and the right child meaning "append a 0"; here it would be the other way around.
To summarize, here's a list of the (nontrivial) involved trees and the relations between them. Here, "B" stands for "binary", "Z" stands for "Zeckendorf", "D" stands for "dual Zeckendorf", and "J" stands for "bijective binary". The first letter describes the representation used to make the numbers in the tree, while the second letter represents the shape of the tree (note "J" is not a separate shape from "B"). And Beren's original tree I'm just going to label "TB" because uh I dunno. :P
List of involved trees, excluding trivial trees (those whose reading sequences are just consecutive whole numbers or positive integers):
TB: Beren's original tree. Has 1 as the root.
DB: Dual-Zeckendorf binary tree. Has 0 as the root.
BD: The original double-or-increment tree. Has 1 as the root.
JD: Double-and-increment-or-just-increment tree. Has 0 as the root.
BZ: Double-or-increment tree, but reversed. Has 1 as the root.
ZB: Zeckendorf binary tree. Has 1 as the root.
Relations among involved trees:
TB = DB + 1
BD = JD + 1
BD = flip(BZ)
TB and BD have inverse reading permutations (starting from 1).
DB and JD have inverse reading permutations (starting from 0).
ZB and BZ have inverse reading permutations (starting from 1).
Um, I realize that's likely a bit confusing, but I hope it clears things up somewhat? Here's a diagram:
inverse
DB(0) ------- JD(0)
|-1 |-1
| |
|+1 inverse |+1
TB(1) ------- BD(1)
|
|flip
inverse |
ZB(1) ------- BZ(1)...where the left column is binary trees with Fibonacci contents, and the right column is Fibonacci-shaped trees with binary contents.(One would of course get more relations if one looked at reverse reading permutations, where you read each row right-to-left, but I don't see a need to discuss that... all that is implied from the above.)
Now you'll notice that nowhere above did I discuss bijective Zeckendorf, because, well, it doesn't seem to really fit into the above very well. But I do have something to say about it, that answers my other two questions from last time!
So, one of the things that's special about binary, that doesn't hold for higher bases, is the close relation between ordinary binary and bijective binary. Namely, for n≥1, the bijective binary for n-1, is the same as the binary for n, but with the leading 1 removed and with 1 added to each digit.
Bijective Zeckendorf was frustrating me because I expected there to be a similar relation, but I wasn't seeing one. Except, oops, it's actually really easy, not sure how I missed it! Namely, for n≥2, the bijective Zeckendorf for n-2, is the same as the Zeckendorf for n, but with the leading 10 removed and with 1 added to each digit. This immediately answers both of my questions about bijective Zeckendorf from the previous post! As in the case of binary, one can see this either by examining how sums of Fibonacci works, or by examining how counting works.
So, yay, all three questions answered! Now when I have some time I need to go make a webpage about this...
