ユーザー:Koteitan/下書き

\( \newcommand{\len}{ {\rm len}} \renewcommand{\value}{ {\rm value}} \newcommand{\ifu}{ {\rm if}} \newcommand{\gtone}{ {\rm gt1}} \newcommand{\parent}{ {\rm parent}} \newcommand{\diff}{ {\rm diff}} \newcommand{\ancestor}{ {\rm ancestor}} \newcommand{\bm}[1]{ {\boldsymbol　 #1}} \newcommand{\w}{\omega} \newcommand{\e}{\varepsilon} \newcommand{\nat}{\mathbb{N}} \newcommand{\p}{\psi} \)

Y数列の展開ルールの説明

Y数列は足し算と引き算と大きさの比較くらいしか使わないので簡単です。小学生にも分かるように説明しようと思います。

Y数列の形

Y数列は \((a_0,a_1,a_2,\cdots,a_k)\) のように、有限個の要素から成り立つ有限数列の形をしています。例えば、(1), (1,1,1), (1,2,2), (1,2,3), (1,2,4), (1,2,3,4,1,2,3,3,3), (1,2,4), (1,2,4,5,4), (1,2,4,8,9,8), (1,2,4,8,16), (1,3), (1,4,4), (1,1024), という感じです。

Y数列の展開(\(\w\)まで)

Y数列は、ブラケット [] という１つのY数列と１つの整数 n を入力とし、１つのY数列を出力とする関数を使って「展開」をすることができます。あとで方法を書きますが、(1,2,3)[2]=(1,2,2,2)、という感じです。ここから、全てのY数列の展開方法を説明します。

まず一番簡単なのは、右端が 1 であるY数列の展開方法です。右端が 1 であるY数列を展開すると、その右端の1が消えるだけです。(1,1,1,1)[2]=(1,1,1)、(1,1,1,1,1,1)[100]=(1,1,1,1,1)、(1)[300]=() です。この場合にはブラケットの値には依存しません。これでひとまず \(\w\) までのY数列の展開ができます。

次に \(\w\) 以上のY数列の展開を説明します。

親を探す

(1,2,3,4,1,2,3,3,3)[2] を展開してみる

まず、( ) の中の全部の数字について、「親」というもの探します。その数字の左から順番に左に見ていって、初めて自分より小さな数が出てきたらそれが親です。例えば、下図の赤丸で囲まれた 3 の親を探します。

となって、2 が親として見つかります。

1 には親がいません。

ヒドラ図を書く

すべての数字に対してそれぞれの親がどれかを調べて、それを下記のように線でつないで表します。これを Y 数列のヒドラ図と呼ぶことにしましょう。

親の反対を子と呼びましょう。子を親の一段上に書くと書きやすいです。

1 には親がいないので、とりあえず左端の × につないでおきます。

Y数列の展開(\(\varepsilon_0\)まで)

親子の差が 1 である数列は下記の方法で展開することができます。

(1) まずブラケットを１つ増やします。
(2) 一番右の数字を消します。
(3) 消された数字の親に怒りのマークを付けます。（子が殺されたので怒るのです）

(4) 怒った親を含む右部分は、「悪い部分(bad part)」と呼びます。親より左の部分は「良い部分(good part)」と呼びます。

(5) 悪い部分をブラケットの数だけ右にコピーします。

また、一番右の数字が 1 のときは、(1) でブラケットが 1 つ増えた後、1 の親がいないため、その 1 が単に消えて終わります。

ここまでの展開方法は、原始数列システムとほぼ同じです。親との差が 2 以上になるときは、また別のルールがあり、それを次で説明します。

Y数列の展開(\(\varepsilon_0\)～\(\varepsilon_{\omega+1}\))

下記で親子の差が 2 以上である数列の展開方法を説明します。例として (1,2,4)[2]を展開してみましょう。

(1,2,4)[2] の展開

この数列では、親が 2、子が 4\ で、(4-2=2\) なので、親子の差が 2 の数列になります。この場合は、上記のように、(1,2,4) の階差数列である (1,2) という２つめの数列を作って、同じように枝を書いてやります。階差数列 (1,2) を (1,2,4) の対応する枝にの下に書いてやるのが分かりやすいです。この (1,2,4) を「１段目の数列」、その階差数列 (1,2) を「２段目の数列」と呼ぶことにします。
展開するには、まずは、この２段目の数列をいままでと同じルールで展開します。

(1,2) → (1,1,1) となりますね。太字の 1 が bad root です。

そしてそれを使って次は１段目の数列を再構成してやることになります。その前に、１段目の数列も２段目の数列と同じように bad part をコピーする必要があります。

まず、１段目の数列の bad root がどこになるかと言うと、２つ目の数列の bad root に対応する枝の先、つまり、この場合は 2 が１段目の数列の bad root になります。bad root とそれから右が bad part です。この場合は 2 で終わりなので、bad part は 2 だけです。

コピーするときは２段目より少し特殊な方法が必要です。まず、最初の数列 (1,2,4) の bad part の「枝の繋がり方」を分析する必要があります。

bad root の親の場所(IN)と刈られた子のあった場所(OUT)の高さに注目します。IN は bad root より一段下に、OUT は bad root よりも１段上の段にありますね。そして、コピーする際にはこの情報を使って、コピーされた bad part の IN が、ひとつ左の bad part の OUT につながるようにコピーするのです。
このようになります。コピーされた bad part は数字を書かずに、数字は〇にしておきます。形が決まったら、２段目の数列が１段目の数列の階差数列なるように１段目の数列を再構築します。

再構築は全て加算で行うことができましたね。1+1=2, 2+1=3, 3+1=4, という感じです。そして、この１段目の数列が、元の数列を展開した数列となります。(1,2,4)[2] を展開して出来る数列は、(1,2,3,4) ということです。

(1,2,4,1,2,4)[2] の展開

今度は (1,2,4,1,2,4)[2] を展開してみましょう。
ファイル:Koteitan explainy 10.png
ひとつだけ先ほどと違うことがあります。 (1,2,4,1,2,4) の右の1 は親が無いので、階差数列が作れません。この場合は親を×と表記しておきましょう。

あとは同じで、階差数列 (1,2,x,1,2) を [2] で展開して (1,2,x,1,1,1)として、それをもとに１段目の数列を展開します。(1,2,4,1,2,3,4) となります。

ちなみにこれは \(\e_02\) に対応するＹ数列になります。

(1,2,4,4)[2] の展開

次は(1,2,4,4)[2]の展開をやってみます。これはさっきと同じルールで展開できます。

まず、２段目の bad root は、最右 2 の親なので 1 になります。bad part はその右なので、(1,2)になります。これを右にブラケット回コピーします。(1,2,1,2,1,2)になりました。では１段目はどうコピーされるかを考えます。

IN は bad root の一つ下、刈り子は 4 で、親は 2 なので、OUT は bad root の一つ上です。これを IN と OUT を繋いで、枝のコピーをします。

そして、先ほどと同じように、２段目の数字をヒントに、１段目の数列を再構成していきます。枝に対応するところを足し算していきます。2+1=3, 3+2=5, 3+1=4, 4+2=6 という風に、〇が 3,5,4,6 で埋まります。(1,2,4,4)[2]=(1,2,4,3,5,4,6) ということですね。

このルールで \(\epsilon_{\w+1}\) 未満までを展開することができます。