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

Source: http://www-math.mit.edu/~rstan/transparencies/parking.pdf

다음과 같은 상황을 생각한다. $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

(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}$ 가 된다. 여기서 나타나는 수열을 프뤼퍼 코드라고 부른다.

Source: https://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Casarotto.pdf

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

2월 2019
월	화	수	목	금	토	일
« 1월				3월 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28

References

이 글 공유하기:

이것이 좋아요:

관련

답글 남기기 응답 취소