穷举法

矩阵

在 Farris 1970 之前对树结构进行穷举的方法

如果有一个矩阵，字母是阶元 (taxa) 数字是性状 (character)，对于数字，每一列是一个 character

A 00
B 11
C 10
D 02

内部节点穷举

假设目前得到了一个树(A (B (C D))) 那么对于性状1来说，内部节点的可能性就如下

0	A(0) 0 B(1) 0 C(1) D(0)

0	A(0) 0 B(1) 1 C(1) D(0)

0	A(0) 1 B(1) 0 C(1) D(0)

1	A(0) 0 B(1) 0 C(1) D(0)

0	A(0) 1 B(1) 1 C(1) D(0)

1	A(0) 0 B(1) 1 C(1) D(0)

1	A(0) 1 B(1) 0 C(1) D(0)

1	A(0) 1 B(1) 1 C(1) D(0)

上面一共8种可能性，即 $s^{T-1}$ ，其中 s 为状态为一共 2 种，T 为阶元 (taxa) 数量，这里就为 $2^{4-1}=8$ 。

对于第一种可能性，C 到父节点的消耗/步数 (cost/steps)是 1 (1->0) ，B 到父节点的消耗/步数是 1 (1->0) ，所以第一种可能性在 character1 的总 steps 是 2。

而一个树的总 steps 就是所有 character 的总 steps 之和。

树拓扑结构穷举

树的拓扑结构可能性如下

	A B C D

	A C B D

	A D B C