TREE(3)：画树画出来的一个超级无敌变态的大大大大大数

这里TREE就是英文里树木的那个单词TREE，TREE(3)其实是一个函数，函数名称叫TREE，而函数自变量取值是3。

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

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

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

第二个条件，你后面画的树，不能“包含”前面的树。这里“包含”的概念是这样的，比如你后面的树去掉若干叶子后，就是之前的树，用术语说，就是前面的树是这颗树的子树，那就犯规的。但我们这里“包含”的意思要比“子树”的定义更宽泛点，我们还要求以下这种情况也不允许，就是当前的树中如果取若干节点，这若干节点如果可以跟之前的某棵树的节点建立一一对应关系，而且两颗树中，任意对应两个节点的最近共同祖先是同一颜色，那也不允许。所谓最近共同“祖先”的概念也是很好理解的，就是两个叶子同时向根节点回溯，那它们迟早会在某个节点汇合，最迟也是根节点，那这个结点就叫“最近共同祖先”，如果你把树看作一个家谱的话，那你就更好理解了。现在的要求就是，如果两棵树之间，如果对应节点的最近共同祖先是同一颜色，那游戏结束。其实这种“包含”在数学上有个术语叫inf-embeddable. Embeddable 就是可嵌入的意思，这个词搞嵌入式系统的再熟悉不过。INF是什么意思呢，它其实是下确界，或者说最大下界的拉丁文缩写。为什么用这个词，因为如果你把一棵树某个枝条上的节点当做一个大小排序的话，且根节点最小，那么两个节点的最近祖先其实就是最大的且比这两个节点都小的的节点， 所以叫下确界，INF。这就是inf-embeddable的全部意思。

(下图：左边的树包含右边的树)

OK，以上就是画树游戏的全部规则。那我跟大家在节目里演示下，玩玩看。当然很推荐你现在拿支笔和纸，一起来玩玩看，你可以用不同的符号来表示颜色。那我们先从TREE(1)这个游戏开始玩，也就是只用一种颜色，假设你用的是红色。先画第一棵树，那你明显只能画一个根节点是红色。你会发现你没办法再画第二棵树了，因为第二棵树，你最多画两个节点。你重画一个红色的根结点，那跟第一棵树一样，肯定不行。你如果画两个红色节点，那也包含第一棵树，也不行。所以游戏结束，你只能画出一棵树，那我们知道TREE(1)=1。

(下图: TREE(1)游戏示意，右边的树包含左边的树，所以游戏结束。TREE(1)=1)

接下来玩下TREE(2)，用两种颜色，红色和绿色。那你第一棵树，比如还是用红色画一个根节点，第二棵树你如果用绿色画一个根结点，那你会发现你第三棵树就没法画了，因为第三棵树无论怎么画，必然包含第一颗或第二棵树。但我们还有一个更好的做法。那就是第二棵树画成绿色的根节点接一个绿色的叶子。这样，我们第三棵树就可以画成只有一个绿色根结点的树，就一个根。因为我们规则只限制后面的树不能包含前面的树，没有规定前面的树不能包含后面的树。这样虽然我们第二棵树包含了第三棵树，但是第三棵树没有包含之前的树，所以这是允许的。这之后，你会发现你无法再画出第四颗树了。所以TREE(2)=3。

(下图：TREE(2)游戏示例，你最多画出如下三颗树，所以TREE(2)=3)

好TREE(1) ，TREE(2)的游戏我们都玩过了，现在到见证奇迹的时刻了，我们要玩TREE(3)了，比如你可以再加入一个颜色，蓝色。用红，绿，蓝三色来玩这个画树的游戏。你会发现，这次你似乎发挥余地大多了，你可以画非常多的树。我在节目介绍里，也放了TREE(3)游戏开始的12棵树的可能画法：

但是我劝你不要继续了，因为你无法画到它结束的时刻，因为这个TREE(3)的值实在太大了，大到惊天地泣鬼神，比葛林恒数还大。当然，你可能此时会质疑，你怎么证明TREE(3)是一个有限值，而不是无穷大的，也就是我可以无穷的玩下去呢？

这里要用到一个定理，叫克鲁斯科尔树定理。克鲁斯科尔这个名字计算机系的听众又是太熟悉了，克鲁斯科尔算法是考试必考的对不对。克鲁斯科尔算我们计算机系学生膜拜的大神了，他已于2010年去世，这里我们也顺带缅怀一下。我们今天不考最小生成树算法，而是克鲁斯科尔发现的这个树定理。这个定理有个粗糙但简单的说法就是如果你给我无穷多个树，那其中必然有一个树是另一颗的INF-embeddable，同下确界意义上的嵌入。那TREE(3)是一个有限的数其实就这个定理的直接推论了，是不是？

你可能关心TREE(3)这个有限的数到底有多大？不管你信不信，这其实是今天节目最难点了。上一期葛立恒数我用箭号表示法，大概还能说明下葛立恒数有多大，但是在TREE(3)面前，箭号表示法已经完全不管用了。但是我们还是可以参考下，上期我们说了葛立恒数可以用64重箭号表示法来表示，那TREE(3)如果要用多重箭号表示法表示，那需要的层数将远远大于葛立恒数。这大概是我最好的形容了，再往下我都不知道怎么说了，因为再怎么用语言或符号表达，我都感觉都是很徒劳了。当然，如果你有兴趣还是可以上网搜搜有关TREE(3)的符号表示，为了表示它的大，得用各种专门的运算符号才行，虽然这些符号对普通人来说，已经没什么感觉了。

关于TREE(3)还有好玩的一点，就是根据克鲁斯科尔树定理，TREE(4), TREE(5)，TREE(100)都是有限的对不对？那TREE(TREE(3)呢，就是用用TREE(3)个颜色玩这个画树游戏，那它还是有限的。那如果TREE(TREE(3))我如此嵌套TREE(3)重呢? 对这个数我表示我大脑系统崩溃了。

OK，今天有关TREE(3)话题就聊到这了，我还是很喜欢TREE(3)这个数，因为它定义是如此之简单，而且从平淡无奇的TREE(1)，TREE(2）, 到TREE(3)如同宇宙大爆炸式的转变，实在太让人吃惊了。另外各位以后写情书也可以考虑写“我爱你TREE(3)年”等等。