I was just introduced to the TREE() function, by a 2017 Numberphile video.
In it, Tony Padilla explains a simplified version of the calculation of the TREE function: We are building a forests with as many trees as we can, following certain rules. Each tree in the nth forest can't have more than n nodes, and each tree in a forest may not "contain" an earlier tree from the same forest (i.e. it can't be "inf-embeddable"). The maximum number of trees in a forest is TREE(n).
On the way to explaining that TREE(3) is very large, he computes the size of TREE(2) as 3, giving this sequence for the forest (where G is a green node, and R is a red node):
- G
- R-R
- R
However, following the rules as best I can, I can do better:
- G-G
- R-R
- R-G
- G-R
- G
- R
Now, both Padilla and Wikipedia tell me that TREE(2) = 3, while I have only just learnt about the subject, so I know I am wrong - I just don't know why.
Is the explanation in the video over-simplified and I am being misled over the meaning of inf-embeddable? Was there a rule clearly explained in the video that I foolishly misunderstood? Where did I make a misstep?
The first tree in the sequence is only allowed to have at most one node, so your "1. G-G" is invalid.