Parking Function の数は (n+1)^{n-1}

数学

Parking Function、 駐車関数、木

Parking Function

n 台の車(1, \cdots, n) が順番に駐車場に入ってくる。駐車スペースはn個 (1, \cdots, n) ある。
1番目の車から順番に駐車する。i 番目の車は駐車スペース a_i に停めようとする ( 1 \le a_i \le n)。このとき、空いていない場合は a_i + 1、それでも空いていない場合は a_i + 2 と次々に隣に停めようとする。
駐車スペース n も空いていない場合は駐車することができず、（ほかの場所が空いていたとしても）失敗する。どこかに駐車した場合、次の車が入ってくる。

数列 a_1, \cdots, a_n について、n 台すべての車が駐車できる場合、数列aを Parking Function と呼ぶ。

問題

長さ n の Parking Function は何通りあるか求めよ。

例 n=2

3通り。
a = (1, 1)
a = (1, 2)
a = (2, 1)

答え

Parking Function の個数を f(n) とすると、f(n) = (n+1)^{n-1}。

上記の問題の代わりに駐車スペースが円形に並んだような問題を考える。
駐車スペース n+1 を追加して考える。このとき Parking Function とは限らない数列は 1 \le a_i \le n+1 (1 \le i \le n) を満たす (n+1)^n 通りが考えられる。
車は駐車スペース n+1 にも停めようとする。さらに、駐車スペース n+1 が空いていない場合は駐車スペース 1 に戻って停めようとし、空いていない場合は 2, 3, \cdots と同様に停めようとする場合を考える。

この場合であれば全ての車が駐車することができ、最後には駐車スペースが一箇所だけ空いている。
(n+1)^n の数列に対して最後に空く駐車スペースは 1 \cdots n+1 が均等に現れ、それぞれ (n+1)^{n-1} 通り。そして「最後に n+1 が空いている」ことと「a は Parking Function」は同値である。

よって元の問題の答えは f(n) = (n+1)^{n-1}。

f:id:natsugiri:20210529101238p:plain
parking

ケイリーの公式 (Cayley's formula)

n+1 頂点のラベル付き木構造の数は (n+1)^{n-1} であり (ケイリーの公式)、Parking Function と一致する。なので１対１で対応させるようなアルゴリズムの１つを書く。

アルゴリズム

Philippe Chassaing と Jean-François Marckert によるアルゴリズム。
コードの簡単さのため計算量が悪いが、小さい工夫で O(n) になる。

入力：長さ n の Parking Function を満たす数列 a
出力：頂点ラベルが 0, \cdots, n の木構造

Q : 頂点を持つQueue
push(Q, 0)
for k in (1, ..., n) {
  for i in (1, ..., n) {
    if a_i == k {
      add_edge(front(Q), i)
      push(Q, i)
    }
  }
  pop(Q)
}

逆向きの写像は頂点0からBFSする。

終わりに

次の2つの内、1つでも満たすような数列も Parking Function である。

  • 任意の非負整数を加算することを任意の回数行うことで、1,\cdots,n の置換を得ることができる
  • ソートし得られた数列 a' について、任意の i (1 \le i \le n) において 1 \le a'_i \le i が成り立つ

以下は全て (n+1)^{n-1} 通りある。

  • 長さ n の Parking Function の数
  • n+1 頂点のラベル付き木の数
  • n+1 頂点の辺ラベル付き根付き木の数
  • n 頂点のラベル付き根付き森の数

辺ラベル付き根付き木はアルゴリズムで0を根とすれば得られる。
根付き森はアルゴリズムで得られた木の頂点 0 を取り除くことで得られる。
そのほかの (n+1)^{n-1} については A000272 - OEIS。

参考文献