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

1≤ n ≤5に対しては、最小のn記号の超置換の長さは 1! + 2! + … + n! である(オンライン整数列大辞典の数列 A180632)。最初の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 以上であることを証明した[1]。この証明が大衆の関心を引いたのは、2018年10月に数学者計算機科学者のロビン・ヒューストンがツイートして以降である[2][3]。2018年10月25日、ロビン・ヒューストン、ジェイ・パントン、ヴィンス・ヴァッターはこの証明をより洗練させたものをOEISに投稿した[4]

上限編集

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

参照編集

注釈編集

  • 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]。

参考文献編集

  1. ^ Anonymous (2011年9月17日). “Permutations Thread III”. Warosu, a 4chan archive. 2018年10月27日閲覧。
  2. ^ Griggs, Mary Beth. “An anonymous 4chan post could help solve a 25-year-old math mystery”. The Verge. 2018年10月24日閲覧。
  3. ^ Houston, Robin. “A curious situation. The best known lower bound... (1054637891085918209)” (英語). Twitter. 2018年10月27日閲覧。
  4. ^ Anonymous 4chan poster (2018年10月25日). “A lower bound on the length of the shortest superpattern”. OEIS. 2018年10月27日閲覧。
  5. ^ Aaron, Williams. "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv:1307.2549v3
  6. ^ Egan, Greg (2018年10月20日). “Superpermutations”. 2018年10月27日閲覧。

外部リンク編集