De Bruijn 数列 - 頭の整理

De Bruijn 数列に関する問題です．解答は下部に載せました．

問題

$k$ 種の文字から作れる文字列を長さ $n$ の読み枠で左から順に読んでいくとき，同じ文字列が読まれない最長の文字列の長さを $L \left( k , n \right)$ と表す．また， $k$ 種の文字から作れる長さ $n$ の文字列の種類の数を $R \left( k , n \right)$ と表す．また， $k$ 種の文字から作れる文字列を長さ $n$ の読み枠で左から順に読んでいくとき，同じ文字列が読まれない最長の文字列の長さ $L \left( k , n \right)$ となる文字列の種類の数を $S \left( k , n \right)$ と表す．このとき，次の問に答えよ．

１． $R \left( k , n \right) = k^n$ を示せ．

２． $L \left( k , n \right) = k^n + n - 1$ を示せ．

３． $S \left( k , n \right)$ は $k^n$ の倍数であることを示せ．

解答

１．長さ $n$ の文字列のどの位置にも $k$ 種類の文字の置き方があるから，

$R \left( k , n \right) = k^n \ \ldots \left( 1 \right)$

２． $k$ 種の文字 $x_1 , x_2 , \ldots , x_k$ から作れる長さ $n$ の文字列には， $x_{i_{1}} x_{i_{2}} \cdots x_{i_{n-1}} \ \ \left( 1 \leq i_p \leq n \right)$ で始まる文字列と終わる文字列が同数含まれる．よって， $x_{j_{1}} x_{j_{2}} \cdots x_{j_{n-1}} \ \ \left( 1 \leq j_p \leq n \right)$ で始まる文字列から始めて順々に文字列をつないでいき，最後は $x_{j_{1}} x_{j_{2}} \cdots x_{j_{n-1}} \ \ \left( 1 \leq j_p \leq n \right)$ で終わる文字列とすれば， $k$ 種の文字 $x_1 , x_2 , \ldots , x_k$ から作れる長さ $n$ の文字列をすべてつないだ文字列が作れる．この文字列を $A$ とおき， $A$ の右端に $x_1 , x_2 , \ldots , x_k$ のいずれかの文字をつなげると，右端の長さ $n$ の文字列は文字列の中に２つある．よって， $A$ は同じ文字列が読まれない最長の文字列の長さを持つ．そして， $\left( 1 \right)$ より，長さ $n$ の文字列をすべてつないだ文字列は右端に注意すると， ${ \displaystyle k^n + n - 1 }$ の長さを持つ．よって，

$L \left( k , n \right) = k^n + n - 1 \ \ldots \left( 2 \right)$

３． $k$ 種の文字から作れる文字列を長さ $n$ の読み枠で左から順に読んでいくとき，同じ文字列が読まれない最長の文字列の長さを持つ文字列は $x_{i_{1}} x_{i_{2}} \cdots x_{i_{k^n}} x_{i_{k^n + 1}} \cdots x_{i_{k^n + n - 1}} \ \ \left( 1 \leq i_p \leq n \right)$ と表せる．この文字列の $x_{i_{k^n + 1}}$ 以降の文字列を切り取って，始めと終わりの文字列をつなげた $x_{i_{1}} x_{i_{2}} \cdots x_{i_{k^n}}$ からなる輪を作る．この輪を右回り（あるいは左回り）に長さ $n$ の読み枠で読むとき，どこから読み始めても，１周する間に同じ文字列は読まれない．また，読み始めの文字が異なれば，１周読んだ文字列は異なる文字列となる．ゆえに，この輪を右回りに長さ $n$ の読み枠で読むとき， $k^n$ 通りの異なる文字列が読まれることになる．従って， $k$ 種の文字から作れる文字列を長さ $n$ の読み枠で左から順に読んでいくとき，同じ文字列が読まれない最長の文字列の長さを持つ文字列を勝手に一つ取ってくると，それと同じ長さを持つ文字列が勝手に取ってきた文字列も含めて $k^n$ 通り存在する．よって， $S \left( k , n \right)$ は $k^n$ の倍数である．