프뤼퍼 수열(트리 ↔ 수열) 변환기

정점에 1부터 n까지 이름표가 붙은 트리를, 1부터 n 사이의 수 n−2개로 이루어진 수열 하나로 바꾼 것입니다. 남은 잎 가운데 번호가 가장 작은 것을 떼어내며 그 이웃을 적기를 n−2번 되풀이해 만듭니다. 이 대응은 일대일이라 수열에서 원래 트리를 그대로 되살릴 수 있습니다.

케일리 공식이 이 대응에서 곧바로 나옵니다. 수열의 자리는 n−2개이고 각 자리에 1부터 n까지 무엇이든 자유롭게 들어가므로 수열은 정확히 n^(n−2)가지입니다. 트리와 수열이 일대일이니 라벨 붙은 트리도 정확히 n^(n−2)개입니다. 정점이 4개면 16개, 10개면 1억 개입니다.

정점 v의 차수가 「수열에 v가 나온 횟수 + 1」이라는 성질을 씁니다. 한 번도 안 나온 정점이 곧 잎이므로, 수열을 앞에서부터 읽으며 아직 안 쓴 잎 가운데 가장 작은 것을 그 값에 이어 붙입니다. 수열을 다 읽으면 차수가 남은 정점이 정확히 둘이고 그 둘을 이으면 끝납니다.

답을 하나로 정하기 위해서입니다. 아무 잎이나 골라도 트리는 복원되지만, 그러면 같은 트리가 여러 수열로 갈 수 있어 일대일 대응이 깨집니다. 대응이 일대일이어야 개수를 세는 데 쓸 수 있으므로 규칙이 필요합니다.

n = 1이면 수열의 길이가 −1이 되어 정의되지 않습니다. n = 2는 길이 0의 빈 수열이고, 그때 트리는 1–2 하나뿐이라 2^0 = 1과 맞아떨어집니다. 그래서 이 도구는 정점 수를 따로 받아 빈 수열이 「입력을 안 한 것」과 헷갈리지 않게 했습니다.

정점에 이름표가 붙어 있어 1–2–3과 2–1–3을 서로 다른 트리로 세기 때문입니다. 이름표를 떼고 모양만 같으면 하나로 세는 「비라벨 트리」는 개수가 훨씬 적고, 닫힌 식이 없어 훨씬 어려운 문제가 됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 트리와 수열은 이 기기에만 남습니다.