『Kolakoski数列』について

Kolakoski(コラコスキー？)数列という数列を見つけたのでここにまとめておく。

Kolakoski数列とは

Kolakoski数列とは、趣味で数学をしていたアマチュアの数学者『William Kolakoski』の考案した数列である。
Kolakoskiが最初に考えた数列は、
$1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,\cdots$
と言うものであった。

この数列は、数列の同じ数字が連続する個数をならべ数列を作る(物の本によるとこれを『KolakoskiTransformation』と呼んでいたりする)という操作によってよって不変となる数列なのである。

$1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,\cdots$ に対して具体的に上の操作を考える。
kolakoski数列を $\{a_{n}\}$ 上の操作によってできる数列を $\{b_n\}$ とする。
$a_1=1$ で1が"1回"連続するから $b_1=1$ 、
$a_2=2,a_3=2$ と2が"2回"連続するから $b_2=2$ 、
$a_4=1,a_5=1$ と1が"2回"連続するから $b_3=2$ 、
この操作を繰り返していけば $\{a_{n}\}$ と $\{b_n\}$ が一致することがわかる。

情報系の人間にはKolakoski Transformationとはランレングス圧縮の連続回数部分から数列をつくる操作だといえばわかりやすかもしれない。

一般化されたKolakoski数列

Kolakoskiが最初に考案した数列は登場する整数を $\{1,2\}$ の二種としていたがこれを一般化して $n$ 種類の整数が登場する上と同様の性質を持つ数列を考えることができる。
以下に例を上げておく。

$\{1,2,3\}$ の時、 $1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3,\cdots$
$\{2,1,3,1\}$ の時、 $2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 2, 1, 3, 3, 3, 1, 1, 1,\cdots$