1. 概要

本記事では，parking function（駐車関数）と呼ばれる数列の個数を数え上げる問題を解説します．

Parking function はハッシュテーブルの研究などに関連して現れた組合せ論的対象です．またその呼称の通り，駐車場に車を停めるというユニークな問題定式化で知られています．

Parking function の個数は非常に簡潔な式で表され，また問題を円環に拡張するという面白い方法で証明されます．

2. 前提知識

特にありません．

3. Parking function

3.1. 定義

【定義 1】

$n$ を正整数とし，$a=(a_1,a_2,\ldots,a_n)$ を，$1$ 以上 $n$ 以下の整数からなる長さ $n$ の整数列とする．$a$ に対する以下の手続きを考える．

列 $x=(x_1,x_2,\ldots,x_n)$ を $x=(0,0,\ldots,0)$ として初期化する．
$i=1,2,\ldots,n$ の順に次を行う．
- $a_i\leq j\leq n$ かつ $x_j=0$ となるような $j$ であって，最小のものを選ぶ．ただしそのような $j$ が存在しないならば失敗として手続き全体を終了する．
- $x_j$ を $1$ に変更する．
失敗することなく $i=1,2,\ldots,n$ に対する処理が終了したならば，成功として手続き全体を終了する．

この手続きが成功するとき，$a$ は parking function であるという．

上の定義では，数列の言葉で手続きを述べましたが，駐車場と車を用いた次のような言い換えが有名で，本記事の説明でも用います．

【定義 1 の言い換え】

駐車場には $1, 2, \ldots, n$ の区画があり，はじめすべての区画は空いている．これから $n$ 台の車 $1, 2, \ldots, n$ が駐車場を訪れる．それぞれの車 $i$ の運転手には，好みの区画 $a_i$ があり，次のようにして車を停める位置を選ぶ：

$j=a_i,a_i+1,\ldots,n$ の順に区画を訪れる．初めて空いている区画を訪れたときに，その区画に駐車する．空いている区画を訪れなかった場合，失敗となる．

$a=(a_1,a_2,\ldots,a_n)$ が parking function であるとは，上の手続きによって失敗することなく $n$ 台すべての車が駐車できることをいう．

3.2. 具体例

例えば $n=5$ のとき，$(3,2,2,4,1)$ は parking function です．手続きは次の図のように進行し，成功します．

$(3,4,3,4,1)$ は parking function ではありません．手続きは次の図のように進行し，失敗します．

$n=2$ のとき，parking function を列挙すると次のようになります．

$$ (1,1),\quad(1,2),\quad(2,1). $$

$n=3$ のとき，parking function を列挙すると次のようになります．

$$ \begin{aligned} &(1,1,1),\quad (1,1,2),\quad (1,1,3),\quad (1,2,1),\quad (1,2,2),\quad (1,2,3),\quad (1,3,1),\quad (1,3,2),\quad \\ &(2,1,1),\quad (2,1,2),\quad (2,1,3),\quad (2,2,1),\quad (2,3,1),\quad (3,1,1),\quad (3,1,2),\quad (3,2,1). \end{aligned} $$

3.3. 同値な言い換え

【命題 2】

$n$ を正整数とする．$1$ 以上 $n$ 以下の整数からなる列 $a=(a_1,a_2,\ldots,a_n)$ について，次の $4$ つは同値である．

$(a_1,\ldots,a_n)$ は parking function である．
各 $k=1,2,\ldots,n$ について，$a_i\leq k$ を満たす $i$ の個数は $k$ 以上である．
$a$ を昇順にソートしたものを $(b_1,b_2,\ldots,b_n)$ とすると，任意の $k$ について $b_k\leq k$ が成り立つ．
$(1,2,\ldots,n)$ の順列 $p=(p_1,p_2,\ldots,p_n)$ であって，任意の $i$ について $a_i\leq p_i$ を満たすものが存在する．

$\text{2}\iff \text{3}$ は明らかです．$\text{1}\implies\text{4}$ は，$i$ 番目の車が駐車される区画を $p_i$ とすればよいです．$\text{4}\implies\text{2}$ は，$p_i=1,2,\ldots,k$ であるような $i$ が $a_i\leq k$ を満たすことから分かります．

$\text{2}\implies\text{1}$ を示します．$n$ に関する帰納法で示します．$n=1$ の場合は明らかです．$n\geq 2$ として，$n-1$ の場合の主張を仮定して $n$ に対する主張を示します．$a=(a_1,a_2,\ldots,a_n)$ が 2 の条件を満たすとします．

2 の条件から，$a_i=1$ を満たす $i$ は少なくともひとつ存在します．そのようなもののうち最小のものを $i_0$ とします．$i_0<i$ かつ $a_i=1$ であるとき，そのような $a_i$ を $2$ に変更しても，列 $a$ が parking function であるか否かは変化しません．車 $i$ の操作時点で区画 $1$ には車 $i_0$ があるからです．また，そのように $a$ を変更した際，$k=1$ を除き「$a_i\leq k$ を満たす $i$ の個数」は変わらないので，条件 2 は保たれます．したがって，$a_i=1$ を満たす $i$ が $i_0$ のみである場合に証明すればよいです．

この場合には，列 $a$ から $a_{i_0}$ を削除し，残った値をすべて $1$ ずつ小さくしたものを $a'$ とすると，

$a$ が parking function であることと，$a'$ が parking function であることは同値であり，
$a$ が条件 2 を満たすことと，$a'$ が条件 2 を満たすことは同値である

ことが容易に分かります．したがって，$a'$ について帰納法の仮定を適用することで，$a$ が parking function であることが示されます．$\blacksquare$

参考

【命題 2】 4 の条件は，完全マッチングの存在として定式化できます．parking function の手続きは，最大マッチングを貪欲に求める手順と対応します．また【命題 2】 2 との同値性は，完全マッチングの存在に関する Hall の定理から導出することもできます．

4. 数え上げ

【定理 3】

$n$ を正整数とするとき，parking function $(a_1,a_2,\ldots,a_n)$ の個数は $(n + 1) ^ {n - 1}$ である．

この定理を証明するために，駐車の手続きを円環に拡張します．$\boldsymbol{0}$ 以上 $n$ 以下の整数からなる数列 $a=(a_1,a_2,\ldots,a_n)$ に対する次の手続きを考えます．

駐車場には $0, 1, 2, \ldots, n$ の区画があり，はじめすべての区画は空いているとする．$n$ 台の車 $1, 2, \ldots, n$ が駐車場を訪れる．それぞれの車 $i$ の運転手には，次のようにして車を停める位置を選ぶ．
- $j=a_i,a_i+1,\ldots,n,0,1,\ldots,a_{i}-1$ の順に区画を訪れ，その区画が空いているならばその区画に駐車する．

$a_i$ として $0$ を許容していること，区画として $0$ も考えていることなどに注意してください．また，それぞれの車はすべての区画を訪れるため，手続きが失敗することはありません．最終的には $n+1$ 個の区画のうちちょうど $1$ 個の区画が使われずに余ることになります．

数列 $a$ は全体で $(n+1) ^ n$ 個あり，対称性よりどの区画 $i$ についても，区画 $i$ が使われないような $a$ の個数は等しいです．したがって，どの区画 $i$ についても，区画 $i$ が使われないような $a$ の個数は $(n+1) ^ {n-1}$ 個です．

特に区画 $0$ が使われないような $a$ の個数は $(n+1) ^ {n-1}$ 個あります．これがそのまま parking function の個数となります． $\blacksquare$

なお，上の証明はほとんどそのまま次の命題に拡張することができます．

【命題 4】

$n,m$ を $m\leq n$ を満たす正整数とする．$1$ 以上 $n$ 以下の整数からなる長さ $m$ の整数列 $a=(a_1,a_2,\ldots,a_m)$ であって，次の条件を満たすものの個数は $(n+1-m)(n+1) ^ {m-1}$ である．

条件：各 $k=1,2,\ldots,n$ について，$a_i\leq k$ を満たす $i$ の個数は $m-n+k$ 以上である．

証明は【定理 3】と同様なので，省略します． $\blacksquare$

5. 関連問題

問題へのコメント

1 は parking function に向きをつけたという設定の問題です．本記事で扱ったように，円環に拡張するという方法を用いると，簡潔かつ，公式解説にあるよりも良い計算量で答が求められます．

2 は parking function を用いて上手く計算すると解ける数え上げ問題です．

3 は木上の parking function という設定の問題です．本記事の結果が解法に役に立つわけではありません．

4 は $A_i=L$ とした場合が parking function の数え上げと同一なので，parking function の数え上げを一般化することが要求されているとも言える難問です．解法としても，parking function の数え上げを用いるものがあります．

6. まとめ

本記事では，parking function の数え上げについて解説しました．このような数え上げは，そのまま出題しても実験して規則を予想するだけで解けてしまうため，出題は多くありませんが，その証明は数え上げ分野の中でも特に綺麗で面白いものだと思います．楽しんでいただければ幸いです．

また数え上げに詳しい方の中には，結論となる値 $(n+1)^{n-1}$ を見て，ラベル付きの木や森の数え上げを想起した方も居ると思います．実際，parking function と根付き木森の間に全単射を作ることで【定理 3】を示す方法も知られています．このような話題については文献 2, 3 などを参照してください．

7. 参考文献

Alan G. Konheim, Benjamin Weiss．An Occupancy Discipline and Applications．SIAM Journal on Applied Mathematics．Vol. 14．No. 6．pp. 1266–1274．1966．DOI: 10.1137/0114101．https://doi.org/10.1137/0114101．
António Guedes de Oliveira, Michel Las Vergnas．Parking Functions and Labeled Trees．Séminaire Lotharingien de Combinatoire．Article B65e．2011．https://www.mat.univie.ac.at/~slc/wpapers/s65guedlas.pdf．
Richard P. Stanley．Parking functions．MIT Mathematics．https://math.mit.edu/~rstan/transparencies/parking.pdf．

トップページ：AtCoder Algorithm Lectures