BEST定理

辺 $e_j$ の $C$ での番号 $j$ を $\mathrm{pos}(e_j)$ と書く。$u\neq w$ とし、$\ell(u)=e_j$ とする。$t(e_j)=:u'$ とおく。
$u'\neq w$ なら $\mathrm{pos}(\ell(u'))>j$ であることを示す。$u'\neq w$ なので $j< m$ である（$t(e_m)=i(e_1)=w$ だから）。よって $e_{j+1}$ があり、$i(e_{j+1})=t(e_j)=u'$ である。$\ell(u')$ は $u'$ から出る辺のうち最後のものなので、$\mathrm{pos}(\ell(u'))\ge j+1$ である。
とくに $e_j$ がループなら $u'=u\neq w$ で、$\ell(u)$ より後に $u$ から出る辺があることになり、$\ell(u)$ の選び方に反する。よって $\ell(u)$ はループでない。$F_C$ は条件 1 を満たす（$u\neq w$ からは $\ell(u)$ だけ、$w$ からは出ない）。$F_C$ に有向閉路 $u_0\to u_1\to\dots\to u_s=u_0$ があれば、各 $u_k$ は $w$ でなく（$w$ から出る $F_C$ の辺はない）、上で示したことから $\mathrm{pos}(\ell(u_0))<\mathrm{pos}(\ell(u_1))<\dots<\mathrm{pos}(\ell(u_s))=\mathrm{pos}(\ell(u_0))$ となって矛盾する。よって条件 2 も満たす。$\square$

順序の組．$w$ に向かう有向全域木 $F$ と、各頂点 $v$ から出る辺の並べ方 $\sigma_v$（$\deg^+(v)$ 本の辺の並び）の組 $(F,(\sigma_v)_v)$ で、次を満たすものを $F$ に合う並べ方 とよぶ。

• $v\neq w$ では、$\sigma_v$ の最後の辺は $v$ から出る $F$ の辺である。
• $v=w$ では、$\sigma_w$ の最初の辺は $e$ である。
  各 $v$ について、残りの $\deg^+(v)-1$ 本の並べ方は自由なので、$F$ に合う並べ方は $\prod_v(\deg^+(v)-1)!$ 通りある。Euler 巡回の集合から、このような組の全体への全単射を作れば、主張が従う。

巡回から組へ．$e$ から始まる Euler 巡回 $C$ に、lem-best-last-exit の $F_C$ と、各 $v$ から出る辺を $C$ に現れる順に並べた $\sigma_v$ を対応させる。$\sigma_v$ の最後は $\ell(v)\in F_C$、$\sigma_w$ の最初は $e_1=e$ なので、これは $F_C$ に合う並べ方である。$C$ は $(\sigma_v)$ から決まる。実際、$e_1=e$ であり、$e_1,\dots,e_j$ が決まれば、$e_{j+1}$ は $\sigma_{t(e_j)}$ の中で、それまでに $t(e_j)$ から出た辺の次の辺である。よってこの対応は単射である。
組から巡回へ．$F$ に合う並べ方 $(\sigma_v)$ を与える。辺 $e$ を通って出発し、その後は、いま居る頂点 $v$ から出る未使用の辺のうち $\sigma_v$ で最も前のものを通る、という規則で進み、居る頂点から出る未使用の辺がなくなったら止まる。こうして得た辺の列を $W$ とする。
(a) $W$ は $w$ で止まる。途中で頂点 $v\neq w$ に居るとき、$W$ は $v$ に入った回数が $v$ から出た回数より $1$ 多い（出発点が $w$ なので）。入った回数は $\deg^-(v)=\deg^+(v)$ 以下なので、出た回数は $\deg^+(v)$ 未満であり、$v$ から出る未使用の辺が残っている。
(b) $W$ はすべての辺を使う。止まった時点で $w$ から出る辺はすべて使われている。各頂点で入った回数と出た回数は等しい（$W$ は $w$ から出て $w$ で終わる）。未使用の辺が残ったとし、未使用の辺が出ている頂点の集合を $U$ とする。$w\notin U$ である。$u\in U$ なら、$\sigma_u$ の順に辺を使うので、最後の辺 $f_u\in F$ は未使用である。$f_u$ の終点 $u'$ について、$u'$ に入った回数は $\deg^-(u')$ 未満なので、出た回数も $\deg^+(u')$ 未満で、$u'\in U$ である。こうして $U$ の頂点から親をたどると $U$ の中にとどまるが、親をたどれば $w\notin U$ に着くので矛盾する。
(a)(b) により $W$ は $e$ から始まる Euler 巡回である。作り方から、$W$ が各 $v$ から出る辺の順は $\sigma_v$ であり、$v\neq w$ から最後に出る辺は $\sigma_v$ の最後の辺、すなわち $v$ から出る $F$ の辺である。よって $F_W=F$ であり、$W$ は前段の対応で $(F,(\sigma_v))$ に写る。逆に前段の $C$ から作った組にこの手続きを当てると、$C$ と同じ規則で辺が選ばれるので $C$ に戻る。2 つの対応は互いに逆である。
$F$ の選び方は $\tau_w(D)$ 通りなので、$\varepsilon(D,e)=\tau_w(D)\prod_v(\deg^+(v)-1)!$ である。$\square$

各頂点 $w$ は出次数が $1$ 以上なので、$w$ から出る辺 $e$ がある。設定で見たとおり $\varepsilon(D,e)=\mathrm{ec}(D)$ は $e$ によらない。thm-best-main の右辺の積は $w$ によらない正の整数なので、$\tau_w(D)=\mathrm{ec}(D)/\prod_v(\deg^+(v)-1)!$ も $w$ によらない。最後の等式は設定の $\tau_w(D)=\det L[w]$ による。$\square$

$L$ の各行の和は $0$ なので、すべての成分が $1$ のベクトルは固有値 $0$ の固有ベクトルである。固有多項式は $\det(\lambda I-L)=\lambda\prod_{j\ge2}(\lambda-\mu_j)$ と書け、$\lambda$ の 1 次の係数は $(-1)^{N-1}\mu_2\cdots\mu_N$ である。一方、$\lambda I-L$ の各列を $\lambda\mathbf e_v$ と $-L$ の列の和とみて行列式を列ごとに展開すると、$\lambda\mathbf e_v$ を 1 つの列 $v$ だけで選んだ項の和が $\lambda$ の 1 次の項で、その係数は $\sum_{w}\det\bigl((-L)[w]\bigr)=(-1)^{N-1}\sum_w\det L[w]$ である。よって $\sum_w\det L[w]=\mu_2\cdots\mu_N$ である。cor-best-root により左辺の各項は $\tau(D)$ なので、主張を得る。$\square$

頂点 $x=a_1\cdots a_{n-1}$ から出る長さ $n-1$ の歩道は、各段で末尾に足す文字 $c_1,\dots,c_{n-1}$ で決まる。1 段ごとに語の先頭が 1 文字ずつ落ちるので、$n-1$ 段の後の頂点は $c_1\cdots c_{n-1}$ である。よって $y=b_1\cdots b_{n-1}$ に着く歩道は $c_j=b_j$ のものただ 1 つである。$(A^{n-1})_{xy}$ は $x$ から $y$ への長さ $n-1$ の歩道の個数なので $1$ である。$\square$

$N:=k^n$ とし、添字は $N$ を法として読む。Euler 巡回 $(e_1,\dots,e_N)$ では $t(e_{j-1})=i(e_j)$ なので、$e_{j-1}$ の第 $2$〜$n$ 文字は $e_j$ の第 $1$〜$n-1$ 文字に等しい。くり返すと、$e_j$ の第 $q$ 文字は $e_{j-(n-q)}$ の第 $n$ 文字 $s_{j-n+q}$ である。よって $e_j=s_{j-n+1}\cdots s_j$ であり、$s$ の連続する $n$ 文字は辺 $e_1,\dots,e_N$ を 1 回ずつ並べたものなので、$s$ は de Bruijn 列である。
逆に de Bruijn 列 $s$ から $e_j:=s_{j-n+1}\cdots s_j$ とおくと、$e_{j-1}$ の終点 $s_{j-n+1}\cdots s_{j-1}$ は $e_j$ の始点に等しく、$e_1,\dots,e_N$ は相異なる $N$ 個の語、すなわち $B(k,n)$ の辺全体なので、$(e_1,\dots,e_N)$ は Euler 巡回である。2 つの対応は互いに逆で、巡回的なずらしを巡回的なずらしに写すので、類どうしの一対一対応を与える。$\square$

$M:=k^{n-1}$ を頂点の個数とする。$n=1$ では $\tau(B(k,1))=1$（1 頂点なので有向全域木は空集合だけ）で、$\mathrm{ec}=(k-1)!=k!/k$ である。
$n\ge2$ とする。lem-best-walk により $A^{n-1}=J$ である。$A$ の固有値を重複を込めて $\lambda_1,\dots,\lambda_M$ とすると、$A$ を上三角化すれば分かるように $A^{n-1}$ の固有値は $\lambda_1^{n-1},\dots,\lambda_M^{n-1}$ である。$J$ は階数 $1$ でトレースが $M$ なので、固有値は $M$（1 個）と $0$（$M-1$ 個）である。よって $0$ でない $\lambda_j$ はちょうど 1 つである。各行の和が $k$ なので $k$ は $A$ の固有値であり、$A$ の固有値は $k$（1 個）と $0$（$M-1$ 個）である。$L$ の対角成分は $k-A_{xx}$、非対角成分は $-A_{xy}$ なので $L=kI-A$ で、$L$ の固有値は $0$（1 個）と $k$（$M-1$ 個）である。
$B(k,n)$ は lem-best-walk により任意の 2 頂点が歩道で結ばれるので連結で、均衡しているから Euler 巡回をもつ（Euler閉路 の命題「有向 Euler 閉路の条件」）。prop-best-eigen により $\tau(B(k,n))=k^{M-1}/M=k^{k^{n-1}-n}$ であり、cor-best-root により
$$ \mathrm{ec}\bigl(B(k,n)\bigr)=k^{k^{n-1}-n}\bigl((k-1)!\bigr)^{k^{n-1}}=\frac{(k!)^{k^{n-1}}}{k^n} $$
である。prop-best-debruijn-euler により、これが巡回 de Bruijn 列の個数である。
巡回 de Bruijn 列 1 つは、ずらしの異なる $k^n$ 個の de Bruijn 列からなる。実際、$s$ を $d$（$0< d< k^n$）だけずらした列が $s$ に等しければ、位置 $j$ と $j+d$ の連続する $n$ 文字が等しくなり、de Bruijn 列であることに反する。よって de Bruijn 列の個数は $k^n$ 倍の $(k!)^{k^{n-1}}$ である。$\square$