다음과 같은 상황을 생각한다. 대의 자동차들이 있고,
개의 주차 스팟
이 일렬로 주어져있다. 각각의 자동차마다 선호하는 주차스팟이 하나씩 있으며,
번째 자동차의 선호 스팟을
라 한다. 이 자동차들이 일렬로 들어가며 각각 차례로 원하는 스팟에 주차하되, 만약 그곳에 다른 차가 이미 있었다면 다음 스팟에 주차를 시도한다고 한다. (만약 다음 스팟에도 차가 있으면 그 다음 스팟을 보는 식) 이런 식으로
대의 자동차 모두 주차할 수 있게 하는
을 주차함수(parking function)라고 부른다.
일 때의 주차함수는 111, 112, 121, 211, 113, 131, 311, 122, 212, 221, 123, 132, 213, 231, 312, 321으로 총 16가지가 나온다.
이 parking function임은 곧
들을 크기 순으로 재배치한 것을
이라 할 때
들이 서입해야함과 동치임을 쉽게 알 수 있다. 그러면 이러한 주차함수의 개수는 어떻게 나오는가? 1959년, 그 개수는
이 됨을 Pyke가 증명했고[1] 그 이후로 이에 대한 조합적 증명들이 몇 나왔다.
그 중 Pollak의 증명이 유명한데, (1974) 번째 스팟을 마련하고 선형의 스팟들의 양끝을 붙여 원형으로 만들고 맨 처음 주어진대로 1번째 스팟에서부터
대의 자동차들이 차례로 주차하는 상황을 생각한다. 그러면 반드시 모든 차가 주차에 성공하게 되며,
가 주차함수임은 빈 공간이
임과 동치임을 알 수 있다. 그런데 만약
을 통해
번째 자동차가
번째 위치에 주차할 수 있게 됐다면,
을 통해(단 mod
로 생각함)
번째 자동차는
번째 위치에 주차하게 됨을 알 수 있다. (역시 mod
) 따라서
들끼리 동치류를 형성한다고 하면 각 동치류마다 1개만 주차함수가 되어 그 개수는
이 된다.
한 편, Cayley의 공식에 의하면 개의 점
이 있을 때 이 점들로 만들어지는 수형도의 개수가
임이 알려져 있다. (꼭지점들을 구분한다는 것을 주의한다. 이런 수형도를 labelled tree라 하는데, 편의상 이 글에서 “수형도”라 함은 이 labelled tree를 가리키도록 한다) 필연적으로 주차함수의 개수는
개의 점들로 이루어지는 수형도의 개수와 같아지는데, 이 둘 사이의 일대일대응을 찾을 수 있을지에 대해 생각해볼 수 있다. 그 일대일대응 중 하나로 Chassaing과 Marckert의 증명을 살펴보도록 한다.[2]
편의상 자동차들을 으로 둔다. 각 스팟
에 대해 그 스팟을 선호하는 자동차의 집합을
로 둔다. (즉
) 그러면
가 주차함수가 되는 것은 곧 모든
에 대해
가 성립함과 동치여야 한다.
주어진 들을 이용해서 수형도를 만들려고 한다. 먼저 점 0을 하나 만들어 이를 root로 설정하고, 현재 위치도 이 0으로 설정한다. 이제
의 원소들을 현재 위치 밑으로 크기 순으로 차례대로 왼쪽에서 오른쪽으로 연결한다. 그리고 같은 층에 있는 오른쪽 다음 원소로 (만약 오른쪽 끝이면 아래 층의 맨 왼쪽 원소로) 현재 위치를 이동하고
의 원소들을 앞에서처럼 연결시킨다. 이 행위를 계속 반복한다. 즉, 그래프를 너비우선(breadth-first)으로 탐색하면서 밑으로 children을 연결한다고 생각하면 된다.

Source: https://www.theoremoftheday.org/CombinatorialTheory/Parking/TotDParking.pdf
그러면 그 결과가 0을 root로 하는 rooted labelled tree가 되는 것이 곧 모든 에 대해
가 성립함과 동치라는 것을 알 수 있다. 따라서 주차함수와 이 0을 root로 하는
개의 점을 갖는 수형도와 동치인데, 임의의
개의 점을 갖는 수형도가 곧 0을 root로 하는 수형도가 되므로 그 개수는 케일리의 공식에 의해
이 된다.
수형도의 개수를 알려주는 이 케일리의 공식도 여러 증명들이 있다. “Proofs from the BOOK”에서도 몇 가지 증명들을 다룬 적이 있다. 그 중 가장 많이 알려진 증명은 Prüfer에 의한 이른바 프뤼퍼 코드(Prüfer code)를 이용한 증명. (1918) 주어진 수형도에 대해 차수(연결된 변 개수)가 1인 점들 중 그 label이 최소인 점 를 잡고,
와 연결된 유일한 점의 label을 기록한다. 그 후
, 그리고
와 연결된 유일한 변을 지운다. 이를 되풀이하면 길이
의 수열을 얻는데, 마지막엔 반드시 점
이 남아야 하므로 이 수열의 마지막 수는 반드시
이어야 한다. 따라서 이
을 지우면 각각의 항이 1 이상
이하인 정수인 길이
의 수열이 되는데, 역으로 이런 수열이 주어지면 이 수열이 만들어지는 수형도를 만들 수 있다. 따라서 수형도의 개수는 수열의 개수
가 된다. 여기서 나타나는 수열을 프뤼퍼 코드라고 부른다.
Pitman은 더블 카운팅을 이용해 증명하기도 했다.[3] 개의 점
이 주어져있을 때, 이들로 이뤄지는 rooted directed labelled tree를 생각한다. 즉 앞에서처럼 root
을 갖는 rooted labelled tree인데, 각각의 변에는 방향성이 주어져있는 것이다. 단 그 방향성은 무작위가 아니다. 수형도는 임의의 점
에 대해
에서 시작해
로 향하는 경로는 유일하게 존재해야 하는데, 그 경로를 따라가면서 화살표가 일관적으로 같은 방향을 향하도록 해야 한다. (즉
) 우리가 세고자 하는 경우의 수는, 이 rooted directed labelled tree들의
개의 변에도
의 label을 매기는 경우의 수
이다.
labelled tree의 개수를 이라 하면, 각각의 수형도마다 root를 선택할 경우의 수가
이고, root가 결정되면 모든 변의 방향이 결정되므로 이 변들에 label을 매기는 경우의 수
까지 곱하면
이다.
한 편, 이번엔 아무 변도 없는 상태에서 변 을 순서대로 놓는다고 생각한다. 변
를 놓는 경우의 수를
라 하면, 일단
을 얻는다. 점 1개만 있는 그래프도 수형도라 생각하면, 처음 상태에는
개의 수형도가 주어져 있고 변을 하나 놓을 때마다 수형도 개수가 하나씩 주어든다고 볼 수 있다. 따라서
개의 변을 놓은 상태에서
개의 rooted directed labelled tree들이 주어져 있다.
번째 변의 시작점
을 택하는 경우의 수는
이고, 그 끝점은 반드시
개의 root들 중
가 있는 수형도의 root를 제외한
개들 중 하나여야 한다. 따라서
가 되므로
가 되므로,
, 곧
가 성립한다.
References
[1] R. Pyke, “The Supremum and infimum of the Poisson process” Ann. Math. Statist., 30 (1959), 568-576.
[2] P. Chassaing and J. Marckert, “Parking Functions, Empirical Processes, and the Width of Rooted Labeled Trees” Electron. J. Combin., 8(1):Research Paper 14, 2001. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r14
[3] J. Pitman, “Coalescent Random Forests” Joutnal of Combinatorial Theory, Series A 85, 165-193 (1999) https://www.stat.berkeley.edu/~pitman/457.pdf