超置換

組合せ数学におけるn記号の超置換（ちょうちかん、）とは、n個の記号の全ての置換を部分文字列として含む文字列である。

1≤ n ≤5に対しては、最小のn記号の超置換の長さは 1! + 2! + … + n! である（）。最初の5つの超置換の長さはそれぞれ 1,3,9,33,153 であり、文字列は具体的には 1 , 121 , 123121321 , 123412314231243121342132413214321 及び以下のものとなる :
 123451234152341253412354123145231425314235142315423124531243
 512431524312543121345213425134215342135421324513241532413524
 132541321453214352143251432154321

下限と上限

下限 
2011年9月、4chanの匿名投稿者がn記号の超置換 (n ≥ 2) の長さは少なくとも n! + (n−1)! + (n−2)! + n − 3 以上であることを証明した。この証明が大衆の関心を引いたのは、2018年10月に数学者、計算機科学者のロビン・ヒューストンがツイートして以降である。2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターはこの証明をより洗練させたものをOEISに投稿した。

上限 
2018年10月20日、アーロン・ウィリアムズが対称群のケイリーグラフのハミルトン路を構成するのに用いた方法を適用することで、グレッグ・イーガンは長さ n! + (n−1)! + (n−2)! + (n−3)! + n − 3 の超置換を生成するアルゴリズムを開発した。2018年までの時点で、これらはn ≥ 7に対して知られている最小の超置換となっている。

参照 

　n個の記号の全ての置換をとして含むような置換。

注釈

参考文献

外部リンク 

 最小超置換問題 - Nathaniel Johnstonのブログ
 

数学に関する記事

組合せ論
置換