https://natsugiri.hatenablog.com/entry/2021/05/29/103109

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。

参考文献

Richard P. Stanley, A Survey of Parking Functions (slide:http://www-math.mit.edu/~rstan/transparencies/parking3.pdf)
Philippe Chassaing, Jean-François Marckert, Parking functions, empirical processes, and the width of rooted labeled trees