tree 3有多大：画树画出一个大数–TREE(3)漫谈

画树画出一个大数–TREE(3)漫谈

大家好，上期我们讲了一个大数，叫葛立恒数。今天我们再接再厉，再讲一个超大数，叫TREE(3)。这里TREE就是英文里树木的那个单词TREE。TREE(3)其实就是一个函数，函数名称叫TREE，而函数自变量取值是3。

上期讲过，TREE(3)跟葛立恒数比的话，葛立恒数是属于忽略不计的。更为神奇的是，TREE(3)的定义比葛立恒数更简单，简单来说，它就是一个画“树”的游戏，树林的树。这里，这个“树”的概念，对计算机专业的听众来说再熟悉不过了，什么二叉树，查找树等等。如果你不是计算机专业的，也不要紧。你应该也看到过公司的组织架构图，或是某个人的家谱等等，也是用类似一棵树的结构展示的，这就是我们今天要谈的树的概念。我在节目介绍里也放了一个树的简单示意图。

然后TREE(3)这个数，就可以用一种画树的游戏来导出，画的时候，我们会给每个节点，俗称叶子的东西，画上某种颜色。而对线段，俗称树枝，我们不关心它的颜色。而TREE(3)，意思就是用三种颜色来画这颗树。

我们还有一些画树的规则。这个画树的游戏只有两个规则。第一条规则是这样，你画的第一棵树，只能有一个节点，第二棵树，不能超过2个节点，第三棵树不能超过3个节点…第n棵树，不能超过n个节点。也就是，越到后面，你树中的节点可以越来越多，但不能多过你画的树的序号。

第二个条件，你后面画的树，不能“包含”前面的树。这里“包含”的概念是这样的，比如你后面的树去掉若干叶子后，就是之前的树，用术语说，就是前面的树是这颗树的子树，那就犯规的。但我们这里“包含”的意思要比“子树”的定义更宽泛点，我们还要求以下这种情况也不允许，就是当前的树中如果取若干节点，这若干节点如果可以跟之前的某棵树的节点建立一一对应关系，而且两颗树中，任意对应两个节点的最近共同祖先是同一颜色，那也不允许。所谓最近共同“祖先”的概念也是很好理解的，就是两个叶子同时向根节点回溯，那它们迟早会在某个节点汇合，最迟也是根节点，那这个结点就叫“最近共同祖先”，如果你把树看作一个家谱的话，那你就更好理解了。现在的要求就是，如果两棵树之间，如果对应节点的最近共同祖先是同一颜色，那游戏结束。其实这种“包含”在数学上有个术语叫inf-embeddable....