超置換
組合せ数学における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が上界になっている。
関連項目
[編集]- 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 March 16, 2014閲覧。
- Houston, Robin (21 August 2014), "Tackling the Minimal Superpermutation Problem", arXiv:1408.5108 [math.CO]。
参考文献
[編集]- ^ Anonymous (17 September 2011). “Permutations Thread III”. Warosu, a 4chan archive. 27 October 2018閲覧。
- ^ Griggs, Mary Beth. “An anonymous 4chan post could help solve a 25-year-old math mystery”. The Verge. 24 October 2018閲覧。
- ^ Houston, Robin. “A curious situation. The best known lower bound... (1054637891085918209)” (英語). Twitter. 27 October 2018閲覧。
- ^ Anonymous 4chan poster (October 25, 2018). “A lower bound on the length of the shortest superpattern”. OEIS. 27 October 2018閲覧。
- ^ Aaron, Williams. "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv:1307.2549v3。
- ^ Egan, Greg (20 October 2018). “Superpermutations”. 27 October 2018閲覧。
外部リンク
[編集]- 最小超置換問題 - Nathaniel Johnstonのブログ
- Grime, James. “Superpermutations - Numberphile” (video). YouTube. Brady Haran. 1 February 2018閲覧。
.svg){kind=small} | この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |