介绍
其实是(prddot{u}fer)序列
什么是prufer序列？
我们认为度数为(1)的点是叶子节点
有一颗无根树，每次选出编号最小的叶子节点，加到当前prufer序列的后面，然后删掉这个节点。直到剩下两个点为止。
这样会得到一个长度为(n-2)，每个数都是(1 ext{~}n)的序列。
可以看出，每棵无根树都对应唯一一个序列。
我们发现，所有叶子节点都不在prufer序列中，一个度数为(d)的点在prufer序列中的出现次数是(d-1)。
那么怎样从一个prufer序列得到一棵树呢？
令(A={1,2,ldots,n})
每次我们选择最小的在(A)中且不在prufer序列中的点(x)，连一条边到prufer序列的第一个点(y)，然后把(x)从(A)中删掉，把prufer序列的第一个数删掉，直到prufer序列为空。这样(A)中还会剩下两个数，在这两个点之间连边即可。
现在我们要证明每个prufer序列都唯一对应一棵树。
因为每个时候(A)的大小都比prufer序列的长度大(2)，所以每次一定能找到一个没在剩下的prufer序列里出现过的数。所以每个prufer序列都对应唯一一棵树。
prufer序列有(n^{n-2})个，所以(n)个点带标号无根树就有(n^{n-2})种。
应用
prufer是一种处理和树有关的计数问题的非常有用的工具。
可以把树的计数问题转成数列的计数问题。.
显然数列的计数比树的计数简单很多。
比如说，一个点的度数最多为(d)，那么这个点在prufer序列中的出现次数(leq d-1)
比如说，生成一个由(k)棵树构成的森林，那么前面(n-k-1)个数可以是(1 ext{~}n)，第(n-k)个数是这(k)个根中的一个，还要乘上选(k)个根的方案数，答案为(inom{n}{k} imes n^{n-k-1} imes k)