parking functions

자동차가 1부터 n까지 잇고 주차구역 1부터 n까지 잇다. 각 자동차 i는 선호구역 p(i)가 잇다. 자동차 1부터 n까지 차례대로 들어간다. 만일 자신의 구역 p(i)가 비어잇으면 그곳에 주차하고 이미 주차되잇으면 다음자리 p(i)+1이 비어잇는지 조사하고 또 차잇으면 또 넘어가고 이런 식으로 모든 차가 주차한다. 만약 n개의 차가 모두 주차에 성공하면 이때 p를 parking function (on [n])이라 한다.

이제부터 하려는 것은 parking function on [n]과 rooted forest on [n]사이의 bijection을 만드는 것이다.

parking function 881233146이 잇다고 하자(예를 들면 p(5)=3). 얘네들은 각각 891234567로 주차가 가능하다.

하나 주목할 것은 만약 아무도 자리 1을 선호하지 않으면 절대 parking function이 될수없다. 그럼 이제 1의 개수가 대응될 forest의 component의 개수라 보고 1을 좋아하는 애를 root라 하는 것이 자연스럽다.

예에서 1을 좋아하는 애는 3과 7.

그다음 2를 좋아하는 애를 조사한다. 여기서 생각할 것은 만일 2가 없고 3부터 쭉 잇다면 3 이상인 수들은 1들과 independent하기 때문에 첫번째 root에다가 3부터 다 달아버리면 될 것이다. 2는 1에 영향을 받으니(2를 좋아하는 애가 3 1 두개때문에 밀려서 3에 주차한다) 두번째 root에 4를 달아버린다.

계속 이런 원리로 recursively 구성해나가면 된다. 계속 해보면 3을 좋아하는 애가 5와 6인데 얘네 둘은 2에 영향을 받진 않는다(받긴 받지만 이는 1을 좋아하는 애들때문에 오는셈이다). 그러니 4밑에 5와 6을 단다. 4를 좋아하는 8이고 얘는 3이 두개이기 때문에 한번 더 밀린다. 따라서 두번째로 3을 좋아하는 애인 6밑에 8을 단다. 5를 좋아하는 애는 없고, 6을 좋아하는 9번차를 보면 얘는 7에 앉는다. 근본적으로 1 좋아하는 애들때메 영향을 받은 것이기에 첫번째 3을 좋아하는 5번차 밑에 단다. 7 좋아하는 애는 없고, 8 좋아하는 1번 2번 차는 각각 구역 8, 9에 주차한다. 기존의 1때문에 아무런 영향을 받지 않은 것이니 첫번째 1을 좋아하는 3번 차 밑에 1과 2를 달아버리면 끝.

만약 rooted forest가 주어지면 위 알고리즘을 토대로 이에 대응하는 parking function을 만들수 잇다.

이거 푼다고 꽤 오래 걸렷는데 이게 저번 조합개론 기말 기출이다 ㅡㅡ

따라서 #parking function on [n] = #rooted forest on [n]

그리고 #rooted forest on [n] = #trees on [n+1](둘 사이에 자연스러운 bijection이 잇다)

#trees on [n+1]은 Cayley formula에 의해 (n+1)^(n-1)개 잇으므로 #parking function on [n] = (n+1)^(n-1)

만약 parking function을 Cayley formula에 의존하지 않고 따로 셀수잇다면 Cayley formula를 증명하게 되는 셈이다.

수학자 Pollak은 이를 다음과 같이 counting하엿다.

주차구역이 1부터 n까지 잇으면 가상의 자리 n+1을 하나 더 만든다. 만일 n+1을 좋아하는데 n+1에 자리가 차잇으면 다시 1번 자리를 조사하는, 원형 구조를 띠게 규칙을 정한다. 이렇게 되면 [n]에서 [n+1]으로 가는 (n+1)^n개의 모든 function은 주차가 가능하다. 자리가 하나씩 비게 되는데 이 빈자리가 n+1일 확률은 정확히 1/(n+1)이다. 따라서 우리가 구하고자 하는 parking function의 개수는 (n+1)^(n-1).

이건 정말 확률론을 이용한 우아한 증명 중의 하나이다. 확률론이 가지는 힘은 정말 큰 듯하다. 눈에 정확히 보이지는 않지만 주어진 구조나 object들의 행동패턴를 이용하여 counting을 하고 어떨 때는 극한값을 계산하기도 하고 존재성을 증명하기도 한다. 확률론도 우아한 매력을 지닌듯하다.