文字列のイヤンホホ化

前書き

ネットミームとしての「イヤンホホ」の扱いについて

某ツイート から、イヤンホホを拡張、一般化する動きがTwitterで盛んに行われている。こういった言葉の変形遊びは、ネットミームなので厳密な変形ルールというものが存在せず、各々がそれらしい拡張ルールによって変形する。
後続が勝手にレギュレーションを指定し、それに則らないものを勝手に批判したり、面白ければ多少のレギュレーション違反も大目に見たりする。

例えばゴツゴツのアハンは流儀が大きく分かれており、中には「ゴツゴツのアハン」をレギュレーション違反とする流儀も存在する。筆者が知る限り、ゴツアハのレギュレーションには以下のようなものがある。

• 2つの異なる文字$a,b$を指定し、文字列内の$a$を$b$に、$b$を$a$に書き換える。
• 複数の異なる文字$a,b,\cdots,z$を指定し、集合$\{a,b,\cdots,z\}$上の置換$\sigma$を用いて、文字列内の各$\xi \in \{a,b,\cdots,z\}$を$\sigma(\xi)$に書き換える。
• 複数の異なる文字$a,b,\cdots,z$を指定し、集合$\{a,b,\cdots,z\}$上の自己写像$\varphi$を用いて、文字列内の各$\xi \in \{a,b,\cdots,z\}$を$\varphi(\xi)$に書き換える。
• 2つの異なる文字$a,b$を指定し、文字列内の$a$のうち1つだけを$b$に、$b$のうち1つだけを$a$に書き換える。
• etc...

このように、言葉遊び系のネットミームは、有名な高々有限個の例から広まるので、如何様にも一般化できてしまう。

長々と話してきたが、結局何が言いたいのかというと、この記事では数学的に面白い方向に一般化をしているだけなので、ネットミームのレギュレーションを規定するものではない。また、「レギュレーションが違う」などというツッコミは、イヤンホホ化操作の定義を明確に書き下した上で、その定義に則ったイヤンホホ化した文字列で僕を笑わせたら聞かないこともない。お笑い自身ニキの挑戦待ってます。

本記事の概略

再帰的イヤンホホ化 について提唱している返信を見た私は、イヤンホホ化の反復について考えた。形式化によって、イヤンホホ化が有限回で停止する場合と、無限ループに陥る場合がある。
この記事では、イヤンホホ化操作の一般化のうち、特に有限回で停止するものをいくつか取り上げる。有限性の証明や、イヤンホホ化が可能な回数などについて議論していく。

イヤンホホ化操作の一覧

Twitterにて確認できたイヤンホホ化操作の定義、及び私が思いついたイヤンホホ化操作の定義を書き下してみる。操作を施す文字列を$S$とおく。

停止しない可能性があるもの

文字列の長さが$2$以上であり、右端が「ん」である文字列$S = S'xん$を、新たに$S'んxx$に書き換える操作

明らかに、$x = ん$ならば操作後はもとの文字列の右に$1$つの「ん」が追加されるのみであり、この操作はいくらでも繰り返せる。
逆に、$x \neq ん$ならば、$S'んxx$に新たに操作を施すことはできない。

文字列の左端以外に「ん」を含む文字列$S = S_0xんS_1$を、新たに$S_0んxxS_1$に書き換える操作

こちらは、$S$に「ん」が2つ以上含まれる場合、可能な限り操作を繰り返すといずれ「ん」が隣り合う状況になる。ここから操作を繰り返すことで、文字列内の「んん」が「んんん」になり、「んんんん」になり、...と無限に繰り返せてしまう。
逆に、「ん」が1文字であれば、操作が可能な回数は「ん」の左にある文字の総数と一致する。

停止するもの

この記事の本題はこちらであるため、ここからはそれぞれに名称を与えよう。

本来のイヤンホホ化操作に近いものは、$2$-末尾「ん」イヤンホホ化操作や$2$-「ん」イヤンホホ化操作である。特に、「ハンズボン」から「ンハハズンボボ」への変形は$2$-「ん」イヤンホホ化操作$2$回でよい。
もはやイヤンホホ操作の面影があまりなく、どちらかというとHigmanの補題の全順序化の整列性を意図したので、最後の操作は潔くイヤンホホを名前から外した。

つまり、Higman操作が有限回で停止することを示せば、これらのイヤンホホ化操作は全て有限回で停止することが示される。

証明の方針として、Higman操作をいくら反復してももとの文字列を部分列にもつ部分列が得られないこと、及びHigmanの補題(どの異なる2元も互いに部分列とならないような、文字列からなる無限集合は存在しない)ことから示す方法と、文字列に順序数という狭義単調減少な無限列を持たない数を割り振って、Higman操作によって割り振った順序数が減少することを示す方法がある。余力があれば両方示したいが、まあこれは探せばいくらでも出てきそうなので執筆は後回しに。

イヤンホホ化操作と停止までの最大ステップ数

各種イヤンホホ化操作は有限回で停止するので、停止までのステップ数を評価したい。しかし、先ほど定義したイヤンホホ化の中には、初期文字列を指定したときに操作回数に上限が与えられるものと、そうでないものが存在する。ここでは前者について述べる。

$n$-末尾「ん」イヤンホホ化操作

文字列$S$の右端が「ん」であり、その左隣が「ん」でない場合は、一度操作を行うと末尾が「ん」でなくなるためこれ以上操作を行えなくなる。この場合、初期文字列$S$から$n$-末尾「ん」イヤンホホ化操作は$1$回しか行えない。
それ以外の、文字列$S$の長さが$1$以下である、文字列$S$の右端が「ん」でない、あるいは右端とその左隣が両方「ん」であるなどの場合は、$S$に対して$n$-末尾「ん」イヤンホホ化操作は行えない。つまり、初期文字列$S$から$n$-末尾「ん」イヤンホホ化操作は$0$回しか行えない。

これ以上操作を行えなくなったときの文字列長は、初期文字列長$|S|$に$n$を足したもので上から抑えられる。

末尾「ん」イヤンホホ化操作

$n$-末尾「ん」イヤンホホ化操作と全く同様に、最大でも操作は$1$回しか行えない。
ただし、どの自然数$n$を用いて$n$-末尾「ん」イヤンホホ化操作を行ったかによって、最終的な文字列長はいくらでも大きくなり、具体的に上限を与えることはできない。

$n$-「ん」イヤンホホ化操作

末尾以外の「ん」でもイヤンホホ操作を行える場合、イヤンホホ化操作の回数は初期文字列に含まれる「ん」の個数によって大きく変わる。
「ん」以外の各文字に対して、それより右に「ん」がいくつ存在するかを考える。右にある「ん」の個数が$0$ならば、その文字に対して$n$-「ん」イヤンホホ化操作は行えない。右にある「ん」の個数が$1$以上ならば、操作を$1$回行ってその文字と「ん」を入れ替える際に、右にある「ん」の個数が$1$つ減り、代わりにその文字が$n$個に増殖する。この$n$個に対して行えるイヤンホホ化操作は等しい。
以上をもとに考えると、右に「ん」が$k$個存在する文字は、$\Sigma_{i < k}n^i = \dfrac{n^k-1}{n-1}$回の$n$-「ん」イヤンホホ化操作によって(増殖したものも全て含めて)これ以上操作ができない状態となる。

あとはこれについて総和を取ればいい。初期文字列$S$について、$S$に含まれる「ん」の個数を$m$、各$i \le m$について、右に「ん」がちょうど$i$個存在する文字の個数を$a_i$とおくと、$S$に対して行える$n$-「ん」イヤンホホ化操作の回数は$\Sigma_{i \le m}a_i\dfrac{n^i-1}{n-1}$回である。
大まかに言えば、文字列内の「ん」の個数に対して、ステップ数は底が$n$の指数関数的に増大する。

$n$-五十音順イヤンホホ化操作

正直ここはかなり自信がないので、あまり信用しないでもらいたい。

おそらく回数を最も多くするためには、操作可能な隣り合った2文字のうちなるべく右のものから計算する方法である。
各文字は、最大でそれより右の文字に対して操作をし切ったときの、右にある五十音順で遅い文字の個数だけ増殖する。
なので、「あいうえおかきくけこ...わをん」みたいな文字列を考えると、まず「をん」が$1$回の操作で「んをを...を」になり、「わんをを...を」が$n^{n-1}$回以上の操作によって「んをを...をわわ...わ」という長さ$n^{n-1}$以上の文字列となり、ということを繰り返していくと、最終的な操作回数は(文字の種類を$k$とおくと)$n\uparrow\uparrow(k-2)$回以上となると思われる。
上限も同様に計算することで、$k$種類の文字を五十音順に並べた文字列に対する$n$-五十音順イヤンホホ化操作の回数は大体底が$n$で高さが$k$のテトレーション程度の大きさになると思われる。

文字の種類を増やさず文字列長を増やした場合、「あいうえおかきくけこ...わをんんんんんん」のように五十音順で最も遅い文字を末尾に連続して並べることで、指数タワーの最上部が更に2乗3乗と増えていき、大まかに言えば[文字の種類]重指数関数程度の増大度となりそうである。

イヤンホホ化操作と停止までの超限ステップ数

上記の場合では、イヤンホホ化操作によって具体的にどれほど文字が増えるかがわかっていた。しかし、例えば「ん」イヤンホホ化操作は、それぞれでいくつ増殖させられるかを決められる。これにより、「ハンズボン」→「ンハハ...ハハズボン」となり、ここから「ハ」の個数以上に操作を繰り返せる。
従って、それぞれの「ん」イヤンホホ化操作がどの正整数$n$を用いて$n$-「ん」イヤンホホ化操作を行ったかによって、停止するまでのステップ数を何回にも増やすことができる。

このようなとき、回数を自然数として具体的には表せないのだが、順序数という、$1$を足す操作と狭義単調増加列の極限に閉じた数体系を用いれば表せる。
正確には、各文字列$S$に対して、$S$の残りの操作回数を$\sup\{Tの残りの操作回数+1 \mid S \longrightarrow T\}$として定めることができる。

「ん」イヤンホホ化操作

文字列$S$について、$\textrm{ord}(S)$を以下のように定める。

• $S$に現れる「ん」の個数を$m$とする。各$i \le m$について、$S$内で右にある「ん」の個数が$i$であるような$S$内の文字の総数を$a_i$とおく。$\textrm{ord}(S) := \omega^{m-1} \times a_m + \omega^{m-2} \times a_{m-1} + \cdots + \omega \times a_2 + a_1$とする。

文字列$S$に対して$n$-「ん」イヤンホホ操作を行った文字列を$S'$とおく。この操作によって順番を入れ替えた「ん」でない方の文字が、その右に$i\ (> 0)$個の「ん」を持っていたとする。$i = 1$ならば、$\textrm{ord}(S) = \textrm{ord}(S')+1$である。$i > 1$ならば、$\textrm{ord}(S')$は$\textrm{ord}(S)$における$\omega^{i-1}$の係数を$1$減らし、$\omega^{i-2}$の係数を$n$増やす。
従って、$S \longrightarrow S'$ならば$\textrm{ord}(S') < \textrm{ord}(S)$であり、$\textrm{ord}(S) = \sup\{\textrm{ord}(S')+1 \mid S \longrightarrow S'\}$である。
($\textrm{ord}(S) = 0$は$S$に現れる全ての「ん」以外の文字が右に「ん」を持たないこと、すなわち$S$に操作が行えないことと同値であることに注意せよ。)
以上により、$\textrm{ord}(S)$は$S$に対する残りの「ん」イヤンホホ化操作回数に等しい。

特に、文字列$S$を動かしたときの残りの「ん」イヤンホホ化操作回数の上限は$\omega^\omega$回である。

五十音順イヤンホホ化操作

五十音順イヤンホホ化操作については、使われている文字の種類によってイヤンホホ化操作の回数が大きく変化する。また、各初期文字列に対して正確な残りのイヤンホホ化操作を求めるのは非常に難しい。(筆者は断念した。)
しかし、$n$種類の文字による文字列の五十音順イヤンホホ化操作回数の上限は簡単に求められたので、ここに書く。
ぶっちゃけるとこの記事で新規性のある部分がここくらいしかない。

上限の導出

文字の種類が$2$種類の場合

便宜上、文字は$0,1$のみとし、$0$の方が五十音順で早いとする。文字列$S$について、$\textrm{ord}_2(S)$を以下のように定める。

• $S$に現れる$1$の個数を$m$とする。各$i \le m$について、$S$内で右にある$1$の個数が$i$であるような$S$内の文字の総数を$a_i$とおく。$\textrm{ord}_2(S) := \omega^{m-1} \times a_m + \omega^{m-2} \times a_{m-1} + \cdots + \omega \times a_2 + a_1$とする。

定義自体はほとんど「ん」イヤンホホ化操作のときと同様である。$\textrm{ord}_2(S)$が$S$の残りの五十音順イヤンホホ操作回数と等しいことも同様に示せる。
「ん」イヤンホホ化操作は「ん」以外の文字を別の文字に置換しても挙動は同じであり、よって「ん」以外の文字を全て同一の文字に揃えた「ん」イヤンホホ化操作のみを考えればよいのだが、これは$2$種類の文字を用いる五十音順イヤンホホ化操作と一致するからである。

特に、$0,1$のみを文字として用いた任意の文字列$S,S'$について、$S \longrightarrow S'$ならば$\textrm{ord}_2(S') < \textrm{ord}(S)_2$であるとする。また、$S$の残りの五十音順イヤンホホ操作回数は$\omega^\omega$回未満である。

文字の種類が$3$種類以上の場合

文字の種類を$n( > 2)$とする。便宜上、文字は$0,1,\cdots,n-1$とし、五十音順の代わりに通常の自然数順序を用いる。
また、$0,1,\cdots,n-2$のみを文字として用いた任意の文字列$S,S'$について$\textrm{ord}_{n-1}(S) < \omega^{\omega \times (n-2)}$が既に定義されており、$S \longrightarrow S'$ならば$\textrm{ord}_{n-1}(S') < \textrm{ord}(S)_{n-1}$であるとする。

$0,1,\cdots,n-1$のみを文字として用いた任意の文字列$S$について、$S$内の$n-1$を$n-2$に置換することで得られる$0,1,\cdots,n-2$のみを用いた文字列を$\textrm{base}_n(S)$、$S$内の$n-2,n-1$以外の文字を削除し、各文字から$n-2$を引くことで得られる$0,1$のみを用いた文字列を$\textrm{HP}_n(S)$と定める。
例えば、$n=4$かつ$S = 0\dot2\dot31011\dot20\dot31\dot30\dot2\dot3\dot2$ならば、$\textrm{base}_4(S) = 0221011202120222$であり、$\textrm{HP}_4(S) = 01011010$である。

特に文字列$S,S'$に対して、$\textrm{base}_n(SS') = \textrm{base}_n(S)\textrm{base}_n(S')$であり、$\textrm{HP}_n(SS') = \textrm{HP}_n(S)\textrm{HP}_n(S')$である。すなわち、$\textrm{base}_n,\textrm{HP}_n$は文字列の結合と可換である。
$0,1,\cdots,n-1$のみを文字として用いた任意の文字列$S,S'$について、$S \longrightarrow S'$ならば、$S = S_0xyS_1,\ S' = S_0y\underbrace{x\cdots x}_k S_1,\ x< y$を満たす文字列$S_0,S_1$と$x,y < n$と正整数$k$が存在する。
$x < n-2$ならば、$y' := \min\{y,n-2\}$とおくと、$\textrm{base}_n(S) = \textrm{base}_n(S_0)xy'\textrm{base}_n(S_1)$かつ$\textrm{base}_n(S') = \textrm{base}_n(S_0)y'\underbrace{x\cdots x}_k\textrm{base}_n(S_1)$なので$\textrm{base}_n(S) \longrightarrow \textrm{base}_n(S')$である。また、$y < n-2$ならば$\textrm{HP}_n(S) = \textrm{HP}_n(S_0)\textrm{HP}_n(S_1) = \textrm{HP}_n(S')$であり、$y \ge n-2$ならば$\textrm{HP}_n(S) = \textrm{HP}_n(S_0)(y-(n-2))\textrm{HP}_n(S_1) = \textrm{HP}_n(S')$なのでいずれにせよ$\textrm{HP}_n(S) = \textrm{HP}_n(S')$である。
$x = n-2$ならば$y = n-1$であり、$\textrm{HP}_n(S) = \textrm{HP}_n(S_0)01\textrm{HP}_n(S_1)$かつ$\textrm{HP}_n(S') = \textrm{HP}_n(S_0)1\underbrace{0\cdots0}_k\textrm{HP}_n(S_1)$なので$\textrm{HP}_n(S) \longrightarrow \textrm{HP}_n(S')$である。

$0,1,\cdots,n-1$のみを文字として用いた任意の文字列$S$について、$\textrm{ord}_n(S) < \omega^{\omega \times (n-1)}$を、$\textrm{ord}_n(S) := \textrm{ord}_2(\textrm{HP}_n(S)) \times \omega^{\omega\times(n-2)} + \textrm{ord}_{n-1}(\textrm{base}_n(S))$として定める。
先に確認した通り、$S \longrightarrow S'$ならば「$\textrm{base}_n(S) \longrightarrow \textrm{base}_n(S')$かつ$\textrm{HP}_n(S) = \textrm{HP}_n(S')$」または$\textrm{HP}_n(S) \longrightarrow \textrm{HP}_n(S')$なので、「$\textrm{ord}_2(\textrm{HP}_n(S)) = \textrm{ord}_2(\textrm{HP}_n(S'))$かつ$\textrm{ord}_{n-1}(\textrm{base}_n(S)) = \textrm{ord}_{n-1}(\textrm{base}_n(S'))$」または$\textrm{ord}_2(\textrm{HP}_n(S)) > \textrm{ord}_2(\textrm{HP}_n(S'))$である。従って、$\textrm{ord}_n(S) > \textrm{ord}_n(S')$である。

あとは$\textrm{ord}_n(S)$についての超限帰納法により、$0,1,\cdots,n-1$のみを文字として用いた任意の文字列$S$について、$S$の残りの五十音順イヤンホホ化回数は$\textrm{ord}_n(S)$以下であり、特に$\omega^{\omega \times (n-1)}$回未満である。
$0,1,\cdots,n-2$のみを文字として用いた任意の文字列$S,S'$について$\textrm{ord}_{n-1}(S) < \omega^{\omega \times (n-2)}$が既に定義されており、$S \longrightarrow S'$ならば$\textrm{ord}_{n-1}(S') < \textrm{ord}(S)_{n-1}$であると仮定していたが、$n$についての帰納法により仮定がなくとも成り立つことがわかる。

下限の導出

任意の$\alpha < \omega^{\omega \times (n-1)}$に対して、残りの五十音順イヤンホホ化回数が$\alpha$回以上である、$0,1,\cdots,n-1$のみを文字として用いた文字列$S$が存在する。概略だけ示そう。
文字列を$n-1$で分割し、最も右にある$n-1$よりも右側を$n-2$で分割し、更に最も右にある$n-2$よりも右側を$n-3$で分割し、ということを繰り返していく。

例えば$n = 5$のときは、

• 文字列$S$を$0,1,2,3$のみを用いた文字列$S_{4,0},\cdots,S_{4,m_4-1}$を用いて、$S = S_{4,m_4-1}\ 4\ S_{4,m_4-2}\ 4\ \cdots\ 4\ S_{4,1}\ 4\ S_{4,0}$と表す。
• 文字列$S_{4,0}$を$0,1,2$のみを用いた文字列$S_{3,0},\cdots,S_{3,m_3-1}$を用いて、$S_{4,0} = S_{3,m_3-1}\ 3\ S_{3,m_3-2}\ 3\ \cdots\ 3\ S_{3,1}\ 3\ S_{3,0}$と表す。
• 文字列$S_{3,0}$を$0,1$のみを用いた文字列$S_{2,0},\cdots,S_{2,m_2-1}$を用いて、$S_{3,0} = S_{2,m_2-1}\ 2\ S_{2,m_2-2}\ 2\ \cdots\ 2\ S_{2,1}\ 2\ S_{2,0}$と表す。
• 文字列$S_{2,0}$を$0$のみを用いた文字列$S_{1,0},\cdots,S_{1,m_1-1}$を用いて、$S_{2,0} = S_{1,m_1-1}\ 1\ S_{1,m_1-2}\ 1\ \cdots\ 1\ S_{1,1}\ 1\ S_{1,0}$と表す。

のようにして文字列の族$\{S_{i,j}\}_{1 \le i < n,\ j < m_i}$を得られる。

文字列$S$、正整数$k$に対して、その文字列が$012\cdots(k-1)012\cdots(k-1)\cdots012\cdots(k-1)$($012\cdots(k-1)$を$m$個反復した文字列)を部分列にもつような最大の$m$を$\textrm{stairs}_k(S)$と表す。
順序数$\textrm{ord}'_n(S) < \omega^{\omega \times (n-1)}$を、$\textrm{ord}'_n(S) := \Sigma_{2 \le i < n,\ j < m_i} (\omega^{\omega \times i + j} \times \textrm{stairs}_i(S_{i,j})) + \Sigma_{1 \le j < m_1} (\omega^{j-1} \times \textrm{stairs}_1(S_{1,j}))$と定める。ただし、$\Sigma$は通常の順序数和ではなく自然和とする。

$S \longrightarrow^{\ge1} S'$で、$S$から五十音順イヤンホホ化操作を$1$回以上繰り返すことで$S'$が得られることを表すことにする。
上記のように$\textrm{ord}'_n(S)$を定めると、任意の文字列$S$と任意の$\alpha < \textrm{ord}'_n(S)$に対して、$S \longrightarrow^{\ge1} S'$かつ$\alpha \le \textrm{ord}'_n(S')$を満たす文字列$S'$が存在することを確かめられる。
あとは$\textrm{ord}'_n(S)$についての超限帰納法により、任意の文字列$S$について、$\textrm{ord}'_n(S)$は$S$の残りの五十音順イヤンホホ化操作回数以上であることが示せる。

特に、$S = 012\cdots\underbrace{(n-1)\cdots(n-1)}_m$のときに$\textrm{ord}'_n(S) = \omega^{\omega \times (n-2) + m}$なので$S$の残りの五十音順イヤンホホ化操作回数は$\textrm{ord}'_n(S) = \omega^{\omega \times (n-2) + m}$以上である。
従って、$n$種類の文字を用いた文字列に対する残りの五十音順イヤンホホ化操作回数は、文字列を動かすことで$\omega^{\omega \times (n-1)}$未満の非有界な値を取りうる。

Higman操作

いずれ書くが、ほとんどHigmanの補題とその順序型が最も大きくなる全順序化の話に終始するので、さっさと知りたい人は 全順序化について詳しく言及されている論文 などを参照してもらいたい。

イヤンホホ化操作のステップ数の有限化

以降は「頑張れば厳密な証明が書ける」と筆者が確信しているにすぎない内容なので、各自疑ってもらいたい。

「有限回しかできないなら具体的に何回なの？」という疑問に対して、前節では「やり方によって変わるからわからないけど、順序数というものを用いれば便宜的にステップ数を表せるよ」という方向で話を進めた。
しかし、具体的な有限の値が出てこないとなんだかモヤモヤする。このようなとき、行う操作にある程度制限をかけることでステップ数に具体的な上限を与える手法があり、有限化と呼ばれる。
(実際はもう少し逆数学的に重要な性質を保つなどの条件が必要みたいで、この記事の例も『有限化』に該当するかはわからないが、便宜上そのように呼ばせてもらう。)

イヤンホホ化操作の回数に上限を与えられなかった要因は、どの正整数$n$について$n$-イヤンホホ化操作を行うかを定めていなかったからである。なので、今回は初期文字列$S$に対して$1$-イヤンホホ化操作、$2$-イヤンホホ化操作、$3$-イヤンホホ化操作、...の順でイヤンホホ化操作を行うことを考える。
こうすればイヤンホホ化操作の回数に明確に上限が与えられる。

各文字列$S$に対して、$S$に対して$1$-「ん」イヤンホホ化操作、$2$-「ん」イヤンホホ化操作、$3$-「ん」イヤンホホ化操作、...、$n$-イヤンホホ化操作を順に行えるような自然数$n$のうち最大のものを、$S$の「ん」イヤンホホ数と呼ぶ。五十音順イヤンホホ数も同様にして定める。
長さ$2$以上かつ、左の方が五十音順で早い隣合った$2$文字が存在する文字列$S = S_0xyS_1\ (x < y)$を、五十音順で$y$より早い文字のみで構成された長さ$n$の文字列$L$を用いて$S_0yLS_1$に書き換える操作を、$n$-Higman操作とよぶことにして、同様に文字列のHigman数というものを定めよう。(ただし、Higman数については始めに文字列$S$内の文字に限らない文字全体の集合を定める必要がある。)

「ん」イヤンホホ数

文字列「イヤホン」に対する「ん」イヤンホホ数は$3$である。
大まかに、$S$の「ん」イヤンホホ数は$S$の中により多くの「ん」が右に現れるような文字が存在するほど大きな数になりやすい。
具体的には、$S$に含まれる「ん」の個数を$m$、$S$内で右にある「ん」の個数が$i$であるような$S$内の文字の総数を$a_i$とおくと、$S$の「ん」イヤンホホ数は$f_m^{a_m}(\cdots(f_2^{a_2}(f_1^{a_1}(0))))$以上である。(おそらく実際にこの値になるが、証明を書き下せる自信がない。)
ただし、各正整数$i$に対して、$f_i$は以下のように定まる関数である。

• $f_1(x) := x+1$
• $f_{i+1}(x) := f_i^{x+1}(x+1)$

例えば、$f_2(x) = 2x+2$であり、$f_3(x) = f_2^{x+1}(x+1) = 2^{x+1}(x+3)-2$である。$f_4$は$f_3$を反復するのでいわゆるテトレーション程度の増大度となる。
文字列「タンタンメン」の「ん」イヤンホホ数は、$f_3(f_2(f_1(0))) = f_3(f_2(1)) = f_3(4) = 222$以上である。
文字列「テンシンランマン」の「ん」イヤンホホ数は、$f_4(f_3(f_2(f_1(0)))) = f_4(222) = f_3^{223}(223) \ge 2\uparrow\uparrow226$以上である。

五十音順イヤンホホ数

文字列「イヤホン」の五十音順イヤンホホ数はそこそこ大きい。

• イヤホン
• イヤンホ
• インヤヤホ

のように進めると、$f_4(2) = f_3^3(3) = f_3^2(94) \ge f_3(2^{100}\times3) \ge 2^{2^{101}}$なので、ここから$2^{2^{101}}$回以上の五十音順イヤンホホ操作を繰り返せるので、「イヤホン」の五十音順イヤンホホ数は$2^{2^{101}}$以上となる。

大まかに、$S$の五十音順イヤンホホ数は、五十音順となる$S$の部分列の最大長が長いほど大きくなりやすい。
「イヤホン」と長さが等しいが五十音順である「アイロン」を例にすると、

• アイロン
• アインロ
• アンイイロ
• ンアアアイイロ
• ンアアイアアアアイロ
• ンアアイアアアイアアアアアロ
• ンアアイアアアイアアアアロア${}^6$
• ンアアイアアアイアアアロア${}^{13}$
• ンアアイアアアイアアロア${}^{21}$
• ンアアイアアアイアロア${}^{30}$
• ンアアイアアアイロア${}^{40}$
• ンアアイアアイア${}^{11}$ロア${}^{40}$

のように続けることができ、少なくとも$3\underbrace{\uparrow\cdots\uparrow}_{3\underbrace{\uparrow\cdots\uparrow}_{2\uparrow\uparrow220}3}3$回以上は続けられる。「アイロン」の五十音順イヤンホホ数は$3\underbrace{\uparrow\cdots\uparrow}_{3\underbrace{\uparrow\cdots\uparrow}_{2\uparrow\uparrow220}3}3$であり、「イヤホン」の時と比べて遥かに大きくなる。

大きな数として有名なものとしてグラハム数が存在するが、例えば「カタリロン」などの五十音順の5文字の文字列の五十音順イヤンホホ数はグラハム数を超える。他にも「ウルトラマン」などでも超えられる。
$n$文字の五十音順の文字列の五十音順イヤンホホ数は急増加関数で$f_{\omega^2}(n-3)$以上の大きさになると思われる。このくらいの増大度の関数として有名なものだと、チェーン表記やふぃっしゅ数ver.1のS変換の反復などがある。

Higman数

文字集合を$\{イ,ホ,ヤ,ン\}$としたときの、文字列「イヤホン」のHigman数について考えよう。

• イヤホン
• イヤンヤ
• ヤイホンヤ
• ヤホイイインヤ
• ヤホイインイヤヤヤヤ
• ヤホイインヤイホホホホヤヤヤ
• ヤホイインヤホイイイイイイホホホヤヤヤ
• ...

この調子で続けていくと、「ヤホイインヤヤヤヤホホ...ホホイイ...イイ」のような文字列となり、ンの右側でHigman操作が行えなくなる。(もっとも、この状態になるまでにグラハム数を優に超える回数のHigman操作を行える。)
ンの右側のHigman操作が停滞するたびに、ンとその左側の1文字でHigman操作をして「ンイヤヤ...ヤヤ」の形にすることで、今まで行ったHigman操作の回数を$n$回とすると、大体急増加関数$f_{\omega^2}(n)$回のHigman操作をンの右側だけで行えるようになると思われる。これを4回行うことで、急増加関数で$f_{\omega^2}^4(\textrm{グラハム数})$回以上のHigman操作が可能である。
すなわち、文字列「イヤホン」のHigman数は$f_{\omega^2}^4(\textrm{グラハム数})$以上になると思われる。

文字の種類が$n$種ある場合、左端の文字以外全て五十音順で最も遅い文字で、左端の文字のみ異なる文字を用いた文字列(あ行のみを用いた文字列なら「あおおおおおお」のような文字列)が、文字の長さに対してHigman数が大きくなる文字列である。このような文字列で長さが$k$のものに対するHigman数は、急増加関数にて$f_{\omega^{n-1}}(k)$程度の速さで増大すると思われる。

後書き

筆者はこのような、文字列操作の反復回数が有限だが非自明に大きくなるという例について考察しており、特に今回の問題はHigman順序を順序型が全順序化した整列集合についての基本列系を簡略化したものに非常に酷似していた。
イヤンホホがまさかHigmanの補題の制限となるとは思わず、本当は自分のツイートがバズってる最中にまとめるつもりが、楽しみすぎて結局2週間もかかってしまった。順序数として$\omega^\omega$や$\omega^{\omega^\omega}$はよく見るのだが、五十音順イヤンホホ操作の回数が$\omega^{\omega^2}$という中途半端な大きさに留まるというのは非常に面白い結果だ。

個人的に、このような中途半端な制限が列だけではなく木や一般のWQOについても拡張できるかどうか、できたとしてどの程度の大きさになるかが気になっている。思いついて気力もあれば続編として書こうと思う。文字列ですらないものに対してイヤンホホ化操作をするとなると、いよいよ一般化のしすぎで怒られてしまいそうだが...。