超置換

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

最小の超置換の具体的な例としては 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に対しては知られている中で最小の超置換となっている。n = 7では2019年時点で( n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3) − 1、5906が上界になっている。

関連項目[編集]

注釈[編集]

  • 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日閲覧。

外部リンク[編集]

スタブアイコン

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

「https://ja.wikipedia.org/w/index.php?title=超置換&oldid=99411772」から取得