超置換

組合せ数学における ${\displaystyle n}$記号の超置換（ちょうちかん、英: superpermutation）とは、n個の記号の全ての置換を部分文字列（substring）として含む文字列で、最小の超置換を求める問題は2025年時点で未解明の数学の難題でもある。

${\displaystyle 1\leq n\leq 5}$に対しては、最小の ${\displaystyle n}$記号の超置換の長さは ${\displaystyle 1!+2!+\cdots +n!}$ に等しい。つまり、順に ${\displaystyle 1,3,9,33,153}$ （オンライン整数列大辞典の数列 A180632）である。

最小の超置換の具体的な例としては ${\displaystyle 1,121,123121321,123412314231243121342132413214321}$ 及び以下のものが挙げられる :

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

一方で、${\displaystyle n\geq 6}$ においても同様の式で長さを求められると予想されていたが、${\displaystyle 6!+5!+4!+3!+2!+1!=873}$ にもかかわらず、Robin Houstonによってその長さが ${\displaystyle 872}$ のものが発見されたため、${\displaystyle 1!+2!+\cdots +n!}$ は ${\displaystyle n\geq 6}$ の ${\displaystyle n}$ に対しては一般に適用されないことが証明されている^[1]。

なお、${\displaystyle n=7}$ および ${\displaystyle n=8}$ の場合もそれぞれ ${\displaystyle 5908}$桁^[2]、${\displaystyle 46205}$桁^[3]のものが確認されており、この数値が最小かどうかは未だ証明されていない。今もさらに短いものを探す試みは継続しており、${\displaystyle n=7}$ においては、2019年2月1日にさらに ${\displaystyle 5907}$桁のものと^[4]、2019年2月27日には ${\displaystyle 5906}$桁^[5]のものが次々と発見されている。

最小超置換の長さ

最小超置換の長さを求める問題は未解決である。

下界

2011年9月、4chanの匿名投稿者が ${\displaystyle n}$ 記号の超置換 ${\displaystyle (n\geq 2)}$ の長さは少なくとも ${\displaystyle n!+\left(n-1\right)!+\left(n-2\right)!+n-3}$ 以上であることを証明した^[6]。この証明は4chanにおいて、アニメシリーズ『涼宮ハルヒの憂鬱』第1期全14話は2006年の放送時は物語の時系列とは異なる順序で放映されたため、エピソードをどの順序で観るのがよいのか、という疑問がきっかけになったことから、『ハルヒ問題』とも呼ばれている。^[7]この証明が大衆の関心を引いたのは、2018年10月に数学者兼計算機科学者のロビン・ヒューストンがツイートして以降である^[8][9]。2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターはこの証明をより洗練させたものをOEISに投稿した^[10]。

上界

2018年10月20日、グレッグ・イーガンは、アーロン・ウィリアムズが対称群のケイリーグラフのハミルトン路を構成するのに用いた方法^[11]を適用することで、長さ ${\displaystyle n!+\left(n-1\right)!+\left(n-2\right)!+\left(n-3\right)!+n-3}$ の超置換を生成するアルゴリズムを開発した^[12]。2018年までの時点で、これらは ${\displaystyle n\geq 7}$ に対しては知られている中で最小の超置換となっている。${\displaystyle n=7}$ の場合、2019年の時点では${\displaystyle \left({n!+\left(n-1\right)!+\left(n-2\right)!+\left(n-3\right)!+n-3}\right)-1}$で、つまり ${\displaystyle 5906}$ が上界になっている。

関連項目

• Superpattern（英語版） - n個の記号の全ての置換をpermutation patterns（英語版）として含むような置換。

注釈

• Ashlock, Daniel A.; Tillotson, Jenett (1993), “Construction of small superpermutations and minimal injective superstrings”, Congressus Numerantium 93: 91–98, Zbl 0801.05004
• Johnston, Nathaniel (July 28, 2013), “Non-uniqueness of minimal superpermutations”, Discrete Mathematics 313 (14): 1553–1557, arXiv:1303.4150, doi:10.1016/j.disc.2013.03.024, Zbl 1368.05004, http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ 2014年3月16日閲覧。
• Houston, Robin (21 August 2014), “Tackling the Minimal Superpermutation Problem”, arXiv:1408.5108 [math.CO]