주차 문제와 케일리의 공식, 그리고 조합적 증명

다음과 같은 상황을 생각한다. n대의 자동차들이 있고, n개의 주차 스팟 1,2,\ldots,n이 일렬로 주어져있다. 각각의 자동차마다 선호하는 주차스팟이 하나씩 있으며, i번째 자동차의 선호 스팟을 a_i라 한다. 이 자동차들이 일렬로 들어가며 각각 차례로 원하는 스팟에 주차하되, 만약 그곳에 다른 차가 이미 있었다면 다음 스팟에 주차를 시도한다고 한다. (만약 다음 스팟에도 차가 있으면 그 다음 스팟을 보는 식) 이런 식으로 n대의 자동차 모두 주차할 수 있게 하는 (a_1,a_2,\ldots,a_n)을 주차함수(parking function)라고 부른다. n=3일 때의 주차함수는 111, 112, 121, 211, 113, 131, 311, 122, 212, 221, 123, 132, 213, 231, 312, 321으로 총 16가지가 나온다.

\alpha = (a_1,a_2,\ldots,a_n)이 parking function임은 곧 a_i들을 크기 순으로 재배치한 것을 b_1 \leq b_2 \leq \cdots \leq b_n이라 할 때 b_i \leq i들이 서입해야함과 동치임을 쉽게 알 수 있다. 그러면 이러한 주차함수의 개수는 어떻게 나오는가? 1959년, 그 개수는 (n+1)^{n-1}이 됨을 Pyke가 증명했고[1] 그 이후로 이에 대한 조합적 증명들이 몇 나왔다.

그 중 Pollak의 증명이 유명한데, (1974) n+1번째 스팟을 마련하고 선형의 스팟들의 양끝을 붙여 원형으로 만들고 맨 처음 주어진대로 1번째 스팟에서부터 n대의 자동차들이 차례로 주차하는 상황을 생각한다. 그러면 반드시 모든 차가 주차에 성공하게 되며, \alpha가 주차함수임은 빈 공간이 n+1임과 동치임을 알 수 있다. 그런데 만약 (a_1,\ldots,a_n)을 통해 i번째 자동차가 p_i번째 위치에 주차할 수 있게 됐다면, (a_1+j,\ldots,a_n+j)을 통해(단 mod n+1로 생각함) i번째 자동차는 p_i+j번째 위치에 주차하게 됨을 알 수 있다. (역시 mod n+1) 따라서 (a_1+j,a_2+j,\ldots,a_n+j)들끼리 동치류를 형성한다고 하면 각 동치류마다 1개만 주차함수가 되어 그 개수는 \frac{(n+1)^n}{n+1}=(n+1)^{n-1}이 된다.

한 편, Cayley의 공식에 의하면 n개의 점 1,2,\ldots,n이 있을 때 이 점들로 만들어지는 수형도의 개수가 n^{n-2}임이 알려져 있다. (꼭지점들을 구분한다는 것을 주의한다. 이런 수형도를 labelled tree라 하는데, 편의상 이 글에서 “수형도”라 함은 이 labelled tree를 가리키도록 한다) 필연적으로 주차함수의 개수는 n+1개의 점들로 이루어지는 수형도의 개수와 같아지는데, 이 둘 사이의 일대일대응을 찾을 수 있을지에 대해 생각해볼 수 있다. 그 일대일대응 중 하나로 Chassaing과 Marckert의 증명을 살펴보도록 한다.[2]

편의상 자동차들을 1,2,\ldots,n으로 둔다. 각 스팟 i에 대해 그 스팟을 선호하는 자동차의 집합을 A_i로 둔다. (즉 A_i=\{j:a_i=j\}) 그러면 \alpha가 주차함수가 되는 것은 곧 모든 k에 대해 \sum_{i=1}^k |A_i| \geq k가 성립함과 동치여야 한다.

주어진 A_i들을 이용해서 수형도를 만들려고 한다. 먼저 점 0을 하나 만들어 이를 root로 설정하고, 현재 위치도 이 0으로 설정한다. 이제 A_1의 원소들을 현재 위치 밑으로 크기 순으로 차례대로 왼쪽에서 오른쪽으로 연결한다. 그리고 같은 층에 있는 오른쪽 다음 원소로 (만약 오른쪽 끝이면 아래 층의 맨 왼쪽 원소로) 현재 위치를 이동하고 A_2의 원소들을 앞에서처럼 연결시킨다. 이 행위를 계속 반복한다. 즉, 그래프를 너비우선(breadth-first)으로 탐색하면서 밑으로 children을 연결한다고 생각하면 된다.

(5,0,1,3,0,5,0,5,7)에 대한 예시. 이 그림에서는 스팟을 0에서부터 셌기 때문에 A_0부터 따지는 등 인덱스가 하나 밀리는 것에 주의한다.
Source: https://www.theoremoftheday.org/CombinatorialTheory/Parking/TotDParking.pdf

그러면 그 결과가 0을 root로 하는 rooted labelled tree가 되는 것이 곧 모든 k에 대해 \sum_{i=1}^k |A_i| \geq k가 성립함과 동치라는 것을 알 수 있다. 따라서 주차함수와 이 0을 root로 하는 n+1개의 점을 갖는 수형도와 동치인데, 임의의 n+1개의 점을 갖는 수형도가 곧 0을 root로 하는 수형도가 되므로 그 개수는 케일리의 공식에 의해 (n+1)^{n-1}이 된다.


수형도의 개수를 알려주는 이 케일리의 공식도 여러 증명들이 있다. “Proofs from the BOOK”에서도 몇 가지 증명들을 다룬 적이 있다. 그 중 가장 많이 알려진 증명은 Prüfer에 의한 이른바 프뤼퍼 코드(Prüfer code)를 이용한 증명. (1918) 주어진 수형도에 대해 차수(연결된 변 개수)가 1인 점들 중 그 label이 최소인 점 v를 잡고, v와 연결된 유일한 점의 label을 기록한다. 그 후 v, 그리고 v와 연결된 유일한 변을 지운다. 이를 되풀이하면 길이 n-1의 수열을 얻는데, 마지막엔 반드시 점 n이 남아야 하므로 이 수열의 마지막 수는 반드시 n이어야 한다. 따라서 이 n을 지우면 각각의 항이 1 이상 n 이하인 정수인 길이 n-2의 수열이 되는데, 역으로 이런 수열이 주어지면 이 수열이 만들어지는 수형도를 만들 수 있다. 따라서 수형도의 개수는 수열의 개수 n^{n-2}가 된다. 여기서 나타나는 수열을 프뤼퍼 코드라고 부른다.

Pitman은 더블 카운팅을 이용해 증명하기도 했다.[3] n개의 점 1,2,\ldots,n이 주어져있을 때, 이들로 이뤄지는 rooted directed labelled tree를 생각한다. 즉 앞에서처럼 root r을 갖는 rooted labelled tree인데, 각각의 변에는 방향성이 주어져있는 것이다. 단 그 방향성은 무작위가 아니다. 수형도는 임의의 점 v에 대해 r에서 시작해 v로 향하는 경로는 유일하게 존재해야 하는데, 그 경로를 따라가면서 화살표가 일관적으로 같은 방향을 향하도록 해야 한다. (즉 r \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v) 우리가 세고자 하는 경우의 수는, 이 rooted directed labelled tree들의 n-1개의 변에도 1,2,\ldots,n-1의 label을 매기는 경우의 수 N이다.

labelled tree의 개수를 T_n이라 하면, 각각의 수형도마다 root를 선택할 경우의 수가 n이고, root가 결정되면 모든 변의 방향이 결정되므로 이 변들에 label을 매기는 경우의 수 (n-1)!까지 곱하면 N = T_n \cdot n \cdot (n-1)! = n!T_n이다.

한 편, 이번엔 아무 변도 없는 상태에서 변 1,2,\ldots,n-1을 순서대로 놓는다고 생각한다. 변 k를 놓는 경우의 수를 n_k라 하면, 일단 n_1=n(n-1)을 얻는다. 점 1개만 있는 그래프도 수형도라 생각하면, 처음 상태에는 n개의 수형도가 주어져 있고 변을 하나 놓을 때마다 수형도 개수가 하나씩 주어든다고 볼 수 있다. 따라서 k-1개의 변을 놓은 상태에서 n-k+1개의 rooted directed labelled tree들이 주어져 있다. k번째 변의 시작점 v을 택하는 경우의 수는 n이고, 그 끝점은 반드시 n-k+1개의 root들 중 v가 있는 수형도의 root를 제외한 n-k개들 중 하나여야 한다. 따라서 n_k=n(n-k)가 되므로 N = \prod_{k=1}^n n_k = n^{n-1}(n-1)!가 되므로, n!T_n = n^{n-1}(n-1)!, 곧 T_n=n^{n-2}가 성립한다.

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

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중