????????上一篇專欄的證明過程確實有很多的bug，所以這次來個二周目。（這樣我就可以再水一篇專欄了?(?^o^?)?）

*文中帶刪除線的地方對于各位學(xué)術(shù)巨佬可能是廢話，可以自行跳過。如果對不帶刪除線的內(nèi)容有不理解的地方，可以看一下這些內(nèi)容。

? ? ? ? 首先，讓我解釋一下cv11662452中的一種超排列遞推構(gòu)造方法的原理，這個原理是我在研究所的廁所中想到的，至今還沒有人正式發(fā)布過∠( ? 」∠)＿。（構(gòu)造法?http://www.notatt.com/permutations.pdf ）

? ? ? ? 先回顧下這個構(gòu)造過程▽

????????n=0時，0個元素的全排列只有“”，而超排列“”就包含了這個全排列，長度為0，不能再短了（長度不能是負數(shù)）。

? ? ? ? 經(jīng)過眾多院士和計算機的不懈努力下，證明出n=1時，最短超排列就是“1”，長度為1。（“1”的全排列只有“1”，而超排列“1”就包含了這個全排列，長度為1，長度為0的數(shù)字串無法包含這個全排列，不能成為超排列，所以……）

????????以此為基礎(chǔ)構(gòu)造出n>1的超排列。（不一定最短）

????????構(gòu)造方法：從左往右看，按出現(xiàn)的順序依次列出(n-1)的所有的全排列（把初始超排列“拆開”），并且每個排列連續(xù)列兩遍（像“abc”->“aabbcc”這樣）。最后在每組相同的排列間插入數(shù)字“n”（像“aabbcc”->“adabdbcdc”這樣）并把相鄰的不同排列之間重復(fù)的部分刪去（這個步驟相當于是“拆開”的逆向過程）。

????????這是一個從一個有2種符號的超排列中創(chuàng)建一個有3種符號的超排列的圖。

????????知道了構(gòu)造方法后，就可以開始構(gòu)造了?(?^o^?)?

(“ ”->“1”:“ ”->“??”->“ 1 ”->“1”，此處空格不是字符，表示啥都沒有)

“1”->“121”:“1”->“11”->“121”

“121”->“123121321”↓

=================================== :

|(? ???ω??? ?)廠?˙3˙?? ? ? ? ? ?? ? ? ? ? ??? ??? ? ??? ? ?121???:

|????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ??? ? ? ?? ? ? ? ? ? ? ? 121???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ?121???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? 121? ?:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? 121???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? 1?21? ?:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?1?21???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?1?21???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?1?21???:

|?ω?｀)...? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1?2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? 1?2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1?2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1??2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?1??2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? 1???2?1?? :

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ?1????2?1???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? 1? ??2??1???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? 1?? ??2???1?? :

|?˙3˙??(??? ? ???)??˙3˙?? ? ? ? ? ? ? ? ? ? ? ?1???2,2? ? 1???:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? 1? ??2_2? ??1????:

|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1? ??2 _ 2? ? 1?????:

|?? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? 1? ??2? _? 2? ? 1??????:

|????? ?? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?1? ??2???_?? 2?? ?1? ? ?? :

|????? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?1? ???2????_? ? 2? ? ?1? ?? ? ?:

|? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? 11???22? ? _????22? ?11? ??? ?????:

|? ? ? ? ? ? ? ?? ?? ? ? ?1 12? 2? ???_?? ??2 21 1? ? ? ?? ?? ? ? :

|????? ? ? ?? ? ? ? 1? 21? 2????_? ?? 2??12??1? ? ? ? ? ? ? ? ? ? :

|????? ? ??? ? 1?2??1?2?? ?_? ??2?1??2?1? ? ? ? ? ? ? ? ? ? ??????:

|???????? ?12? ? 12????_? ??21? ??21? ? ? ? ? ? ? ? ? ? ? ? ? ? ? :

|???? ? ?12?? ? 12???_???21? ???21? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? :

|? ?? ? 12? ???12?? _???21?? ? 21? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? :

|? ? ? ?12? ????12??_??21? ?? ?21? ? ? ? ? ?? ? ? ? ? ?????? ? ? ?:

|? ??? ? 12???3???12?_?21?? 3? ?21? ? ? ? ? ? ? ?? ? ? ? ?? ? ?? ?:

|?????? ? 12???3???12,21?? 3? ??21? ? ? ? ? ? ? ? ? ?? ??( ˙?˙ ):

|???? ? ? ?12????3?? ?121????3?? ?21? ? ? ? ? ? ? ? ? ? ??( ˙?˙ ):

|???? ? ? ??? ?12???3???121???3???21? ? ? ? ?? ? ? ? ? ? ?( ˙?˙ ):

|???? ? ? ? ? ? ? ?12??3??121??3??21? ? ? ? ? ? ? ???? ? ?( ˙?˙ ):

|???? ? ? ??? ? ? ????12?3?121?3?21? ? ? ? ? ? ? ? ?? ? ??( ˙?˙ ):

|???? ? ? ??? ? ? ? ?? ??123121321? ? ? ? ? ? ? ? ? ? ?? ?( ˙?˙ ):

|_________________________________________________

????????定義為n種符號的以這種構(gòu)造方式構(gòu)造的超排列的長度。通過簡單的分析可以得出

*通過(n-1)(n≥2)種字符的超排列構(gòu)造n種字符的超排列，這個過程相當于原本拆開產(chǎn)生的數(shù)又在拼接時去除，數(shù)的個數(shù)不變。而在兩者之間，復(fù)制出了(n-1)!個1到(n-1)的排列，每個排列有(n-1)個數(shù)此外還有添加的(n-1)!個數(shù)字n，所以多出數(shù)字的總個數(shù)就是：

????????然后用口算就能得出。

????????看到這里你可能滿腦袋問號？？？？？

????????這個過程為什么可以構(gòu)造超排列？

????????為什么這個過程不會出現(xiàn)bug？

????????好的，現(xiàn)在我就來解釋這個構(gòu)造方法的原理▽（和BV14f4y137LU的玉米拼圖解法相似）

????????想要得到1到n(n≥2)的超排列，就要構(gòu)造n!種1到n的排列，那在有1到(n-1)的排列的前提下，怎么插入n才能構(gòu)造呢？

1.先列出1到(n-1)的所有排列（每個列兩遍），然后在每兩個相同排列之間加上數(shù)字n。

2.像節(jié)目[The Price Is Right]這樣（其實和超排列的規(guī)則相似）

????????從左到右依次取n個連續(xù)的數(shù)字，你會發(fā)現(xiàn)n個1到n的排列。

????????對每個（共(n-1)!個）排列都這樣做，就能得到(n-1)!×n=n!個不同的排列，也就是1到n的全排列。（因為框框必須包含數(shù)字n，又因為“拼接”和“拆開”是對稱操作，不涉及數(shù)字n，而且“拼接”后每個n兩邊的排列不變，所以在“拼接”過程中不會產(chǎn)生重復(fù)的排列也不會“損失”排列，進而得知構(gòu)造1到(n+1)的排列時第一步?jīng)]有bug）

*如果框框的位置不同，那么排列一定不同，因為數(shù)字n的位置不同。

*如果數(shù)字n兩邊的1到(n-1)的排列不同，那么排列也一定不同，因為如果排列相同，那么把它們所在的框框分別移到最左邊（右邊）所得到的排列一定相同，即數(shù)字n左邊（右邊）的1到(n-1)的排列相同。（把框框移到左邊〔右邊〕相當于把框框內(nèi)數(shù)字n右邊〔左邊〕的部分Ctrl+X（"X"代表剪刀）再Ctrl+V（"Viscidity"（粘性的））到框框左邊〔右邊〕，要么都不是〔〕中的內(nèi)容，要么都是〔〕中的內(nèi)容）

????????1到n的全排列是有了，那“拼接”會不會有問題呢？

????????不會，由于每個數(shù)字n兩邊的排列不同，所以不能把數(shù)字n拼在一起，不然兩邊的排列對不上不能拼，因為排列的每個數(shù)字只出現(xiàn)一次，過了這個村就沒這個店，沒過這個村也沒這個店，多“拼”少“拼”都不行，除非你不“拼”（這樣的構(gòu)造法明顯不劃算）。至于其它陰間的拼法就不深入討論了。可以但沒必要，只是為了構(gòu)造。

? ? ? ? 所以只要按“拆開”的反向操作“拼接”就行（“拆開”時每個排列都要與兩邊的排列分離，而“拼接”只要和一邊接在一起就行了，顯然沒問題）

????????好了，這種構(gòu)造法就解釋完了。（之后不再討論n=0的情況，因為確實沒有必要）

????????4chan的網(wǎng)友（大佬）得出的涼宮春日問題下界（目前已知最大的下界）是這個

????????接下來我就用深入淺出的方法來解釋這個下界的由來。

? ? ? ? 這用的是?https://oeis.org/A180632/a180632.pdf?的推導(dǎo)過程，而該論文又出自?https://mathsci.fandom.com/wiki/The_Haruhi_Problem?（該網(wǎng)站還引入了兩個簡單下限的證明，這兩個下限是和）

????????現(xiàn)在我給出這兩個簡單下界的證明過程（會數(shù)數(shù)的人應(yīng)該都看得懂）

Quiz:把n種字符排序，一共有多少種排法？

????????先從n種字符中取下一個字符放在序列的開頭，一共有n種選法，然后在剩下的(n-1)字符中再取下一個字符放在序列的第二個位置，一共有(n-1)種選法，一直到最后一個字符都取下并放入序列為止。根據(jù)分步乘法計數(shù)原理得，總方法數(shù)是從1到n的所有整數(shù)的積，即n!（n的階乘）。（“按某種順序依次取下字符并選一個序列的空位放入”的方法也是可以的，但是不能以“任取字符放入任選位置”這樣的方法分析，因為這樣計數(shù)會有重復(fù)）

????????于是，n種字符的全排列有n!種。為了完成超排列，就必須把這些排列排列（可以刪去重復(fù)部分），任選一個排列放在序列的開頭，之后若要引入新的排列，至少得添加一個字符（當?shù)谝粋€排列的最后(n-1)個字符和添加的第一個字符連成一個新的排列時，就可以只添加一個字符）。因為每種排列都是不一樣的，所以必須通過添加字符來引入新的排列。那么添加剩下的(n!-1)個排列就至少添加個字符（最好每次添加一個字符就引入一個新的排列，就可以只添加(n!-1)個字符）。

????????顯然，當n較大時，只添加(n!-1)個字符是不可能完成超排列的，因為“通過添加一個字符引入一個排列”的方法只有把上一個排列的第一個字符Ctrl+C（"Copy"）&Ctrl+V到最后（因為一個排列中沒有重復(fù)的字符）。不難發(fā)現(xiàn)，“加一個字符就引入一個新排列”這樣的事件不可能連續(xù)發(fā)生n次，即使連續(xù)發(fā)生(n-1)次，第n次也一定不會發(fā)生。

????????要想完成超排列，就得從某個初始排列開始，引入(n!-1)個新排列，因為上述結(jié)論，所以最理想的辦法可以是先進行(n-1)次“加一個字符并引入一個新排列”再進行一次“加兩個字符并引入有且僅有一個的新排列”，一直重復(fù)到所有排列都出現(xiàn)為止。此時“加兩個字符并引入一個新排列”的事件的次數(shù)是[(n!-1)÷n=(n-1)!-1…n-1]次（n=1時，事件的次數(shù)是0次，規(guī)定0!=1，把n=1代入該余數(shù)除法算式，得"0÷1=0…0"，確實是0次，這體現(xiàn)了規(guī)定0!=1的好處），所以“加一個字符并引入一個新排列”的事件的次數(shù)自然就是次，算上初始排列的長度n，就可以得出一個更好的下限，即

*我認為這樣算更快—>（添加字符的總次數(shù)加上添加兩個字符的次數(shù)，添加一個字符的次數(shù)只計入一次，而添加兩個字符的次數(shù)計入了兩次）。

接下來介紹?https://mathsci.fandom.com/wiki/The_Haruhi_Problem?對兩個簡單下界的證明↓

? ? ? ? 他定義了這樣幾個量↓

L:字符串的實時長度（字符個數(shù)）

N?:字符串中不同排列的實時個數(shù)

令X?=L-N?

X?一開始就是(n-1)（第一個排列的長度n減去排列的個數(shù)1），N?+1（引入一個新排列），L必須至少+1（必須添加字符才能引入新的排列）。

????????所以隨著字符串的加長，ΔL≥ΔN?，ΔX?≥0，于是X?≥n-1。所以，當超排列完成時，

????????我們在幼兒園就……坐過圓桌。和之前一樣，n個小朋友坐有n個座位（每個座位都不一樣）的圓桌有n!種坐法。如果只考慮小朋友之間的相對位置，那么一共有幾種坐法呢？考慮其中一種坐法，以任意一名小朋友為起點，按順時針方向給小朋友排隊，因為有n個小朋友，所以有n種排法，也就是說這個問題的一種坐法對應(yīng)了n個小朋友排隊的n種排法，而n個小朋友排隊共有n!種排法，所以該問題的答案乘以n等于n!，得出該問題的答案是(n-1)!（在0!=1的規(guī)定下，n=1時仍成立）。

????????n種字符的圓排列數(shù)是(n-1)!（n=1時仍成立，下同），所以我們可以把n種字符的n!種排列分成(n-1)!堆，每堆（在上述網(wǎng)站中被稱做"1-loop"）都有n個對應(yīng)一種圓排列的排列，這時定義N?為包含已引入的排列的堆的個數(shù)。

????????從某一堆的某個排列開始，只添加一個字符，要么引入這個堆中的排列（把這個排列的第一個字符Ctrl+C&Ctrl+V到最后），要么不引入排列（加其他字符）。所以如果要引入其他堆的排列，只添加一個字符是不夠的。

????????定義X?=L-N?-N?，若N?+0（不引入像上圖中B堆這樣的“新堆”），N?+1（引入一個新排列），L必須至少+1（參考上一個下限的證明）。所以，ΔL≥ΔN?+N?，即ΔX?≥0。（和上一個下限的證明過程一樣）

????????若N?+1（引入“新堆”）則N?必須+1（引入“新堆”的排列） ，并且ΔL≥2（加一個字符是不夠的）。所以，ΔL≥ΔN?+N?，即ΔX?≥0。

????????簡單的說，為了讓N?+1，L必須至少+2，所以X?永遠不會減少。

????????因為初始情況下，N?=1（只有初始排列），N?=1（包含初始排列的堆有且僅有一個），X?=n-2。當超排列完成時，N?=n!（和上面一樣），N?=(n-1)!（n種字符的圓排列數(shù)）。也就是說，因為必須引入(n-1)!個堆的所有排列，所以當超排列完成時，

? ? ? ? 我忍不住了，所以決定在解釋最后的下限之前，先補充下?https://mathsci.fandom.com/wiki/The_Haruhi_Problem?網(wǎng)頁中的一些概念：（和圖論相似）

????????可以把超排列想象成一個有向圖，每個排列是一個節(jié)點，連接節(jié)點的“箭頭”是排列間的轉(zhuǎn)換過程（把某個排列的前若干個字符Ctrl+X&（選中的字符串的字符，下同）調(diào)整順序&Ctrl+V到后面，并盡量減少剪切字符個數(shù)）。盡量用最少的字符引入一個新排列，這對其他“箭頭”是沒有影響的（可以參考上文對超排列遞推構(gòu)造法過程的解釋，或者這樣理解：某個“箭頭”“長度”（剪切字符個數(shù)）變化，但兩端的節(jié)點（排列）是不變的，也就是說，前一個“箭頭”的終點和后一個“箭頭”的起點不變，同樣地，其他“箭頭”也不變），這樣只會減少L，所以是合理的，也就是說“箭頭”是唯一的（取最短），如果過程中引入了其他排列，即“箭頭”“穿過”了其他節(jié)點，則把這個過程分成多個過程，也就是把“箭頭”沿節(jié)點“斷開”，這樣只會引入更多的排列并可能減少L，所以它是合理的。

1-edg(EDGNB)e相似于最簡單的“箭頭”，它指的是，通過把某個排列的第一個字符Ctrl+C&Ctrl+V到最后來引入一個排列。

2-edge是指通過把某個排列的前兩個字符Ctrl+C&調(diào)換順序&Ctrl+V到最后來引入一個排列。（如果不調(diào)換順序的話就等效于兩個1-edges了，沒有意義）

x-edge是指通過把某個排列的前x個字符Ctrl+C&調(diào)整順序&Ctrl+V到最后來引入一個排列（可以分解成若干個小edges的x-edges除外），下文中的x-edge是指通過把某個排列的前x個字符Ctrl+C&倒序（ABC->CBA）&Ctrl+V到最后來引入一個排列，可以把它看作“狹義的x-edge”。

1-loop（使排列成環(huán)，無始無終，下同）是指一些對應(yīng)著同一個圓排列的n個排列的集合，n種字符一共有(n-1)!種圓排列，所以就有(n-1)!個1-loops，如果引入了一個1-loop中的所有排列，就算完成了一個1-cycle（有始有終，下同）。（?https://zhuanlan.zhihu.com/p/150582767 中解釋了loop和cycle的區(qū)別，部分資料沒有對這兩者有明顯的區(qū)分，所以不必太計較）

2-loop是指“任取一個n種字符的排列，作(n-1)次1-edges，再作一次2-edge，重復(fù)這兩個過程（不能調(diào)換順序），經(jīng)過的所有排列的”集合。（2-cycle是啥不用我多說了）

x(x≥3)-loop(cycle)目前還沒有明確的定義，x-loop和x-cycle（可以把它看作“狹義的x-loop(cycle)”）會在下文做解釋。

? ? ? ? 下圖解釋了為什么一個2-cycle(loop)有n(n-1)個排列。

????????現(xiàn)在介紹一下這個網(wǎng)站對第三種下限的證明(n≥2)：

為了在某個過程中的N?+1，必須得完成一個1-cycle，并進入一個新的1-cycle。（周而復(fù)始）假設(shè)起點排列是P，P沿1-edge到達的排列是P'（P'和P在一個1-cycle中），那么P’一定是之前引入過的排列，如果之前是從P'進入P'的1-cycle（此時P'是這個1-cycle的排列中第一個被引入的排列）的話，那么以2-edge離開P不會進入新的2-cycle（如果會的話那P'被引入時算啥，P'被忽視了），會引入和P'處于相同2-cycle的排列，所以要想通過2-edge使N?+1并進入新的2-cycle的話，在出發(fā)點P之前一定引入過P①（不然就違反了該網(wǎng)站的默認規(guī)則），所以上一步到達P（已引入）時N?+0。（由于P已引入，所以“上一步”是存在的）除①外，還有兩種進入新的2-cycle的方法②③。通過x(x≥3)-edge②或者通過2-edge使N?+0③。（這三種方法互斥但不一定可行，但包括了所有進入新的2-cycle的方法）

????????最后，定義N?為進入2-cycle的個數(shù)（像上上上圖中的2-loop，規(guī)定通過非1-edge引入的“藍色排列”時N?+1，同時該“藍色排列”相應(yīng)的2-cycle中的所有“藍色排列”都失去了讓N?+1的能力），X?=L-N?-N?-N?，N?+0時，ΔX?≥0。（參考前面的證明過程）若N?+1，在①情況下，在“上一步”中，L至少+1，N?,N?,N?均+0，在2-edge中，L+2，N?,N?,N?均+1，結(jié)合這兩步，ΔX?≥0。在②情況下，L至少+3，即使N?,N?均+1，仍然是ΔX?≥0。在③情況下，L+2，N?最多+1，N?+0，ΔX?≥0。

????????一開始，X?=n-1-1-1=n-3（和之前差不多），到最后，ΔX?≥0，N?=n!，N?=(n-1)!，N_2≥n!/n(n-1)=(n-2)!(n≥2)（當2-loops之間沒有公共排列時取"="），所以當超排列完成時匿名網(wǎng)友的證明結(jié)束了。（不難發(fā)現(xiàn)，只有N?+1，N?才可能+1，只有N?+1，N?才可能+1）

????????我在 https://b23.tv/c9Dl9y 和 https://b23.tv/mQuy2f 上發(fā)布了Robin Houston發(fā)布的對4chan網(wǎng)友的證明過程改進后的證明過程(n≥2)。

????????當時對2-loop沒有一個清楚的認知，所以各位在看“wt(π?，π???)=2的情況”時可能會有“為什么一定要嚴格按照2-cycle的路徑走？”“這樣也算在一個2-cycle中的話，那v能達到(n-2)!嗎？”等疑惑?？赐炅松鲜龅淖C明過程，這些疑惑自然就解決了，把π?看做P，把σ看做P'，σ和π???都在從σ開始（σ不一定就是這當中第一個被引入的排列）的2-loop，它們都可以看做這個2-loop中的兩個“藍色排列”，這個2-loop中的(n-1)個“藍色排列”都有機會使v（N?）+1。因為每個2-loop由(n-1)個1-loops構(gòu)成，想要完成超排列，就得引入所有的排列，就得進入所有的1-cycles（(n-1)!個），就得至少進入(n-1)!/(n-1)=(n-2)!(n≥2)個2-loops。所以最終v≥(n-2)!。（現(xiàn)在各位再返回去看證明過程應(yīng)該就能理解了）

????????在Robin Houston的證明過程中，把c(π?,…,π?)定義為π?,…,π???過程中完成的1-cycle的個數(shù)，這樣就避免了匿名網(wǎng)友證明過程中出現(xiàn)的“上一個”。但大致思路是一樣的，都是“從一個一個小過程推導(dǎo)到整個過程”。

????????此外，在匿名網(wǎng)友的證明過程中，還提了一句“貪婪的圓環(huán)算法使用越來越大的循環(huán)：它通過(k+1)-edge連接(n-k)個k-loops，以制作(k+1)-loops。但我還沒有能夠證明這些更大的循環(huán)”。（此處暗紅色加粗部分應(yīng)該沒問題）

? ? ? ? 于是……

? ? ? ? “看起來勝利在望！感覺只要我們花足夠多的時間，足夠努力去打磨這個方法，我們最終總能證明，超排列的長度至少是，從而證明這個猜想。事實上，當時每一個了解這個問題的數(shù)學(xué)家，都確信猜想成立。當時有人在MathOverFlow上問這個問題，回答者們甚至都開始討論起輸出超排列的序列的算法了。這個問題甚至還出現(xiàn)在了1998年的土耳其信息學(xué)競賽里?？雌饋碛嬎銠C學(xué)家們已經(jīng)默認我們構(gòu)造出的序列就是超排列了，他們開始關(guān)心如何更快的輸出這個序列了。當時很多數(shù)學(xué)家都在懷疑，這個猜想到底是不是真正‘的未解決的數(shù)學(xué)問題’，還是只是大家懶得去花時間寫下這個人人都認為成立并且簡單的證明?！薄?https://www.zhihu.com/answer/532606339?

????????等一下，各位有沒有發(fā)現(xiàn)，這個（第二種構(gòu)造法）“最短”長度和之前構(gòu)造法（第一種構(gòu)造法）長度是一樣的，其實兩種方式構(gòu)造的超排列可以是一樣的。（我們認定第二種構(gòu)造方法如下下圖，構(gòu)造(n-1)-cycle（看上圖就知道為啥是(n-1)-cycle了），即“為了不斷地引入新排列，在超排列完成之前，1-edge用不了（無法引入新排列，下同）就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”的構(gòu)造，即盡量用短的x-edge，看下下圖就知道了）

????? ? n較小時，一眼就能看出這一點（兩種方式構(gòu)造的超排列可以是一樣的），而且這種超排列的構(gòu)造可以理解為“為了不斷地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”的方式。而第一種方法的遞推過程，可以看做把每個edge都加長1，并把每個排列都變成相應(yīng)的1-cycle（可以理解為“0-edge（？）變成1-edge”）”的過程，所以遞推后“為了不斷地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”這樣的方式仍然適用，用數(shù)學(xué)歸納法的思路，得出第一種構(gòu)造方式就是“為了不斷地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”。不難發(fā)現(xiàn)，“為了不斷地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”這樣的方式就是構(gòu)造(n-1)-cycle的方式，也就是第二種構(gòu)造方式！

? ? ? ? 在 https://www.zhihu.com/answer/532606339 的鼓勵下，我給出了新的下限證明如下：

如果超排列的1,2,3-edges都是按下圖這種規(guī)則構(gòu)造會最短的話，那么3-edge只有一種，就是下圖的紅色箭頭這種，因為其他5種都不行，要么等價于1-edge或2-edge，要么會在第二個2-cycle重復(fù)（不信的話你可以試試看或看下下圖）。

? ? ????那么3-loop的定義也明確了，用之前的方法就可以證明。（可惜加粗部分我不能證明），直到我看到?http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_nsk666646664466646666_2SYMM_FS.txt?（這個網(wǎng)址的"666646…"好像是該超排列中連續(xù)的1-edge數(shù)目，但又仿佛不是……），羅賓·休斯頓（Robin Houston）和格雷格·伊根（Greg Egan）于2019年2月27日給出了n=7的超排列，長度是5906，（羅賓·休斯頓（Robin Houston）還把這個超排列做成了MP3打擊樂 https://s3.boskent.com/superpermutations/7/5906.mp3?）而“我的下限”只有5907。直接否定了我的觀點。

? ? ? ? 在他做打擊樂時，還有這種事：（引用?http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html?的話，有刪節(jié)）

????????為了保持以非傳統(tǒng)方式宣布超排列的傳統(tǒng)，馬特·帕克（Matt Parker）提出在他的一次活動中讓一架自彈鋼琴演奏這首歌（長度是5906的n=7的超排列）來“發(fā)表”這首歌。因此，如果你想親自聆聽這種以七音音階（因為n=7）呈現(xiàn)的超排列，這里有幾個MIDI版本音樂可供選擇：

C小調(diào)，鐘琴→?http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_C_Minor_Glockenspiel.mid?

降B大調(diào)，鐘琴→?http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_B_Flat_Major_Glockenspiel.mid?

C小調(diào)，鋼琴→?http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_C_Minor_Piano.mid?

15種樂器演奏15種不同長度的超級變奏5906→?http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_C_Minor_MultiInstrument.mid?

????????這個超排列是如何發(fā)現(xiàn)的？先來點背景故事。自從羅賓·休斯頓（Robin?Houston）通過旅行商解算器找到了n=6的最短超排列（下面有論文PDF鏈接）后，他和幾位合作者一直在試圖理解和推廣該超排列的結(jié)構(gòu)（以及他后來發(fā)現(xiàn)的數(shù)千個相同長度的超排列）

????????直到最近，這里的最新技術(shù)是從相同n值的標準超排列（通過上文的遞歸構(gòu)造法構(gòu)造的排列）的一部分開始，包括許多完整的3-cycles（此處暗紅色加粗應(yīng)該沒問題，下同）。每個3-cycle是由edges of weight 3(也許是3-edges)連接的（n–2）個2-cycles的序列，（之前講過）而連續(xù)的3-cycle通過edges of weight 4(也許是4-edges)相互連接。通過獲取該初始“內(nèi)核”，然后將其與連續(xù)的2-cycles合并，可以訪問每個置換，至少對于n=6和n=7，總長度為：

????????此前，在2019年2月1日，"查理·維恩（Charlie Vane）"發(fā)現(xiàn)了一個n=7情況下長度是5907的超排列，（在當時）是一個新的記錄！這是在馬特·帕克（Matt Parker）在YouTube上關(guān)于超排列的視頻?https://www.youtube.com/watch?v=OZzIvl1tbPo&lc=UgzxhVwUBG9EyyldHGd4AaABAg.8qeg_FoKqzY8qmPR3OErzH?的評論區(qū)宣布的。

? ? ? ? n=7，5907位數(shù)字，由"查理·維恩（Charlie Vane）"發(fā)現(xiàn)(?http://www.gregegan.net/SCIENCE/Superpermutations/7_5907_CharlieVane.txt )

? ? ? ? 顯然， "查理 · 范恩" 是博格丹 · 科安達（Bogdan Coanda）的網(wǎng)名， 他提供了如何找到這種超級排列的解釋?https://groups.google.com/d/msg/superpermutators/KNhmzQy99ic/obl6pCt5HwAJ 。

????????（引用結(jié)束）

?【【Numberphile】超級排列數(shù)?@圓桌字幕組-嗶哩嗶哩】【視頻標記點?05:19】https://b23.tv/JJXWEu?（在QQ和微信等通訊平臺發(fā)送它并點擊鏈接可以直接到達時間坐標，或單擊05:19進入視頻）

????????接下來就到了最難的部分——最新上界（科幻作家及數(shù)學(xué)家格雷格·伊根（Greg Egan）?通過https://arxiv.org/pdf/1408.5108.pdf?，得知1≤n≤6時最好的上限不是這個，之后他才在網(wǎng)站的后面補充了長度是5906的n=7的超排列，但他好像忘把這個上限的n的范圍改成(n≥8)了）的證明。

????????參考?http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html?的證明過程，這是Greg Egan在2018年10月提出的，他參考了Aaron Williams在2013年設(shè)計的結(jié)構(gòu)。

????????稍微總結(jié)一下↓（再引用?http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html?的話）

（Greg Egan）通過調(diào)整 Aaron Williams（論文PDF?https://arxiv.org/pdf/1307.2549.pdf?，各位量力而行）?在 2013 年設(shè)計的結(jié)構(gòu)，可以生成的超排列的長度是：（比之前的遞推構(gòu)造好）

……

比標準算法或這種新構(gòu)造產(chǎn)生的超排列更短的超排列目前僅在兩種特定情況下（前提是n≥6）為人所知：

• 對于n?= 6，如前所述，Robin Houston 使用解決旅行商問題的算法發(fā)現(xiàn)了長度為 872 的超排列，此后他設(shè)計了新方法，產(chǎn)生了數(shù)千個這種長度的示例。

• 對于n?= 7，Bogdan Coanda 開發(fā)了一種更快的算法，該算法發(fā)現(xiàn)了幾個長度為 5907 的超排列。隨后，休斯頓進一步完善了他的想法，在他的幫助下，我（Greg Egan）能夠?qū)煞N方法結(jié)合起來，找到幾十個?長度為 5906 的超排列。

????????如果我們找到一種構(gòu)造這種長度的排列的方法（Greg Egan提出的每種排列只經(jīng)過一次的構(gòu)造，之前提到過），那上界就不證自明了，然后我看到了這句話：

“為了使 Aaron Williams 在通過對稱群的哈密頓路徑上的工作適應(yīng)構(gòu)造超置換的問題，我們需要縮減圖，使它們只包含1-edges和2-edges 。”

????????只用1-edge和2-edge真的可以嗎？

? ? ? ? 一開始我是不信的，直到我看到了這句話“But his τ?is the permutation 21345...n?that transposes the first two entries”。Greg Egan把?σ （排列變換操作）定義為“1-edge（刪去被復(fù)制的1個字符）”，把 δ （排列變換操作）定義為“2-edge（刪去被復(fù)制的2個字符）”。Aaron Williams對?σ 的定義和Greg Egan的一樣，但是他沒有定義?δ ，而是像上面這句英文這樣，即把?τ （排列變換操作）定義為“把最排列前面的兩個字符調(diào)換順序”。但Greg Egan認為：The good news is that most of the beautiful work that Williams has done with his choice of permutations can be adapted, without much trouble, to use our permutations σ and δ instead.（翻譯：好消息是，威廉姆斯選擇排列所做的大部分優(yōu)美的工作，可以毫不費力地改編，用我們的?σ 和 δ 來代替。）但我不能理解他為啥這么說，我也沒有看到相關(guān)文獻，所以我思考了一下，想出了用?σ 和 δ 代替?τ?的方法：對于n種字符的一個排列（以123...n為例，其他同理），先用1次2-edge，把排列變成3...n21，再用(n-2)次1-edge把前(n-2)個字符放到最后，排列變成213...n，這樣就成功地把前兩個字符交換順序了，也就實現(xiàn)了?τ?。但是他又提出：It turns out that these two permutations are enough to generate the whole group（事實證明，這兩種排列足以生成整個組）。后來我理解了，就像下面這個圖一樣，用1-edges確定交換字符的位置（像下圖的隔板一樣），再用?τ?交換字符，最后用1-edges把隔板“復(fù)位”就可以交換任意兩個相鄰字符的位置（也可以不“復(fù)位”，方便下一次交換）。像冒泡排序那樣反復(fù)操作，就可以變成任意一個排列了。

????????作者用?δ?和?σ?1?（把某排列的最后一個字符Ctrl+X&Ctrl+V到排列的最前面，和“倒著的1-edge”類似）構(gòu)造alternating cycle（可以看做在幾個1-cycles間反復(fù)“交替”橫跳，）。

*對于任意一個2-cycle，提出其中所有的2-edges（共(n-1)個）的兩端的兩個排列，共2(n-1)個排列，可以把它們組成一個alternating cycle，所以一個alternating cycle有2(n-1)個排列。同樣地，把任意一個alternating cycle的所有1-cycle補完整，就得到了一個2-cycle，所以所有的2-cycles和所有的alternating cycles一一對應(yīng)。

????????取(n–1)對循環(huán)連續(xù)數(shù)字(1,2), (2,3), ..., (n–2,?n–1), (n–1,1)。對于每個(r,m)，取1和(n–1)之間不包括(r,m)的符號的排列，因為有(n-1)-2=(n-3)種字符，所以有(n-3)!種排列。因為(r,m)有(n-1)種，所以總共有(n–1)(n–3)!種這樣的排列，作者把它們稱為q（是一個字符串）。所以一種(r,m)對應(yīng)(n-3)!種q，一共有(n–1)(n–3)!種"mnrq（此處省略字符或字符串的連接符，下同）"型排列，并列出以這些"mnrq"型排列為起點的alternating cycles。從上圖的每一個alternating cycle可以看出，1(m)只會左右橫跳，剩下(n-1)種字符連成排列就像1-loop一樣。（*"~"表示連續(xù)的遞增的數(shù)字，如果"~"兩端的數(shù)字相等則合并，若"~"前的數(shù)字比"~"后的大1，則刪去"~"及兩端。123~n→?δ →3~n21→?σ?1 →13~n2→?δ →4~n231→?σ?1 →14~n23→…，1在左右橫跳，加粗部分可以用?σ 連接）要么m在不同的位置，要么剩下(n-1)種字符連成排列不同，要么兩個都不同，總之在任何一個alternating cycle里找到相同的排列。

????????看下方n=4的示意圖，這些以這些"mnrq"型排列為起點的alternating cycles沒有重復(fù)的排列，而這一點是可以證明的↓? ?當幾個起點的m和r相同時，因為q不同，所以對于從任意的幾個這樣的起點開始的alternating cycles分別選出的排列，即使m在同一側(cè)，剩下(n-1)種字符組成的以nrq（q不同）為開始的1-loop肯定不同。當幾個起點的m和r不同時，m?rot(nr?q?)≠rot(nr?q?)m?（此處的rot(?)是以?排列為起點1-cycle的所有排列，比如這個1-cycle rot(1423)={1423,4231,2314,3142}），因為即使通過"rot"使n在相同位置，相應(yīng)的r?和r?也不同。（就算通過"rot"使n在倒數(shù)第二位，就算r?=m?，也不可能令r?=m?，因為n≥4，至少有3個(r,m)）

????????因為m?≠m?，所以m?rot(nr?q?)≠m?rot(nr?q?)，rot(nr?q?)m?≠rot(nr?q?)m?。

? ? ? ? 一共有n!個排列連成環(huán)，所以一共有n!個edges，其中有(n–1)2(n–3)!個2-edges（有(n–1)(n–3)!種alternating cycles，每種alternating cycle有(n-1)個2-edges），那剩下就有[n!-(n–1)2(n–3)!]個1-edges。所以edges的總長度是（可以用總edges的個數(shù)n!加2-edges的個數(shù)[n!-(n–1)2(n–3)!]）? ? ? ? Aaron Williams找到了一種方法，可以把所有的排列連成兩個大環(huán)（想象一下把所有排列做成珍珠，再把珍珠分成兩堆分別串成兩個項鏈），然后按下圖把兩個大環(huán)做成一個超排列。

? ? ? ? 所以最終的上限是

THE END

? ? ? ? 誒，是不是還少了什么，Aaron Williams發(fā)現(xiàn)的這兩個大環(huán)是怎么形成的？還有，為啥它們可以這樣拼在一起？Greg Egan網(wǎng)站的幾個圖片似乎提供了答案。

????????*這幾幅圖的每一個節(jié)點是一個2-cycle，但不一定是以"mnrq"型排列為起點的alternating cycles對應(yīng)的2-cycle。

*這五幅圖中的m|q（m是一個字符，q是一個字符串，注意區(qū)分mnrq和mq）是2-cycles的一種表示方式，它表示以某個"mq"型排列為起點的alternating cycle對應(yīng)的2-loop，顯然m|rot(q)指的是同一個2-loop，即rot(mrot(q))（原因見上），e.x.：

1234 ? 3421 → 4213 → 2134 →
1342 ? 4231 → 2314 → 3142 →
1423 ? 2341 → 3412 → 4123 → back to start

左上方顯示的2周期可以表示為1|234=1|342=1|423。

? ? ? ? 每種alternating cycle都對應(yīng)一個2-loop，第一幅圖形象演示了兩個2-cycles（該圖中左邊那個2-cycle就是左上方這個2-cycle）合并的過程（兩個相同的1-loops合并），按照這樣的規(guī)則，可以把n=4情況下的三個2-cycles合成兩個一大一小的環(huán)。

? ? ? ??第二、三幅圖分別是n=6和n=7的圖。第四幅圖的陰影部分內(nèi)邊界和外邊界分別對應(yīng)兩個環(huán)，一個在正多邊形內(nèi)，還有一個由“沿著樹枝的表皮爬行”得到。第五幅圖是最新的研究進展圖，顯示了8棵2-cycles樹，它們附著在內(nèi)核（上文提過）上以產(chǎn)生超置換，您別說這個圖還有點上下對稱的感覺。（節(jié)點的顏色由"|"前的數(shù)字決定，第二、三、四，的節(jié)點顏色的波長隨"|"前的數(shù)字的增加而減小，多邊形內(nèi)部循環(huán)是逆時針進行的）

? ? ? ? 接下來，考慮n≥4的情況。

*接下來的內(nèi)容會有一點點難，建議小孩和不懂事的大人在家人的陪同下食用。

? ? ? ? 先給出多邊形（內(nèi)部）循環(huán)的構(gòu)造方法：

想找到這個循環(huán)，可能需要構(gòu)造一種排列，步驟以及e.x.如下↓

1. 在rot((n-1)~1)輸出的(n-1)個排列中，任選一種。

2. 在選中的排列的第一和第二個字符中間插入字符n，得到一個有n種字符的排列。

3. 因為步驟1.有(n-1)種選法，所以經(jīng)過步驟2.得到的排列也有(n-1)種。

4. 比如n=6，步驟1.的輸出是54321,43215,32154,21543,15432，經(jīng)過步驟2.得到的排列分別是564321,463215,362154,261543,165432。

????????在得到的每個排列（共(n-1)個）的第一個字符后加上"|",就得到了(n-1)個2-cycles，e.x.n=6時，五個2-cycles是，5|64321,4|63215,3|62154,2|61543,1|65432。

*"~"表示連續(xù)的遞減的數(shù)字，如果"~"兩端的數(shù)字相等則合并，若"~"前的數(shù)字"~"比后的小1，則刪去"~"及兩端。

????????對于2-cycle 2|n1(n-1)~3，從2n1(n-1)~3開始。沿2-cycle彳亍走，得（děi）先執(zhí)行?δ?（原因見上，下同），得1(n-1)~3n2，接著執(zhí)行(n-3)次?σ?，得3n21(n-1)~4。和之前一樣，在得到的排列的第一個字符后加上"|"，就發(fā)現(xiàn)（沒發(fā)現(xiàn)的可以看看之前的步驟）這是之前說的(n-1)個2-cycles中的一個，即3|n21(n-1)~4，可以看做是進入了下一個2-cycle（除n以外的字符都變成了和自己相鄰的下一個字符。特別地，(n-1)的相鄰的下一個字符是1，下同）。一直重復(fù)這個過程（遍歷了這(n-1)個2-cycles），你會發(fā)現(xiàn)，按照上上圖中提到的對稱性，除n以外的字符都在以相同的規(guī)律變化著。在這個過程中，遍歷的這(n-1)個2-cycles可以串在一起。自然地，既然能從這(n-1)個2-cycles中的一個2-cycle進入了“下一個2-cycle”（參考上文，下同），那么這兩個2-cycles就可以融合，而上文的“執(zhí)行(n-3)次?σ ”的過程其實就是沿這兩個2-cycles的公共1-cycle彳亍走。這(n-1)個2-cycles中的每一個2-cycle都和“下一個2-cycle”融合，(n-1)次融合后，一個“多邊形”就生成了。相應(yīng)地，“多邊形”內(nèi)部的這個較小的環(huán)也找到了，參考上文orange部分（經(jīng)過這(n-1)個2-cycles）。換個角度想，你可以先找出這個較小的環(huán)，它遍歷的2-cycles，就是這(n-1)個2-cycles。

*Greg?Egan構(gòu)建多邊形頂點和構(gòu)建附加樹的規(guī)則相當簡單。

????????Greg Egan給出的(n-1)個2-cycles（我的2-cycles"|"后的字符串調(diào)整一下就是他的）：

• Start with the 2-cycle 1|(n–1)...32n

• The second 2-cycle is 2|(n–1)...3n1

• The third 2-cycle is 3|(n–1)...4n21

• （注：想知道Greg Egan怎么表示第(n-1)個2-cycle）

• In our notation?m|q, we successively increase the value of?m, while?q?(modulo rotations) is (n–1)...321 with?n?replacing?m?in the descending sequence. [Note that in the diagram, we have rotated?q?into a canonical position with the lowest digit first.]

再給出外面的大環(huán)——“以多邊形為根生長的樹枝”——的作者的構(gòu)造法（節(jié)點就是2-cycle）（有刪節(jié)）：

*樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，若節(jié)點A往遠離多邊形的方向移動一節(jié)到節(jié)點B，則把節(jié)點A叫做父節(jié)點，把節(jié)點B叫做子節(jié)點。還存在其他使用“父（子）節(jié)點”這兩個詞的情況，見下文

*用m|q（m是一個字符，q是一個字符串）表示2-cycles

*特別規(guī)定1-1就是(n-1)，此處的減法和一般的減法不一樣，它表示沿循環(huán)逆向移動，此處的加法也同理

*下面的有些引理沒有證明，下面這個只能算是終極結(jié)論的證明思路，不過我相信各位可以自行證明這些引理，如果不會的話請評論或私信

• 每個子頂點的m值都比其父節(jié)點小1（特別地，父節(jié)點的m=1時，子節(jié)點的m=n–1）

• 如果我們將父節(jié)點寫為m|(m–1)p，那么它的子節(jié)點是(m–1)|mrot(p)，其中rot是向左旋轉(zhuǎn)?個位置（注：執(zhí)行?次?σ?），?的范圍是從1到n–3。（注：如果各位想要證明子節(jié)點的表示法，可以把p分成兩截，左邊那截長度為?）

• 每個根節(jié)點（注：多邊形上的節(jié)點，可以理解成父節(jié)點）恰好有(n–4)個子節(jié)點，多邊形中的一個鄰居（圖中是順時針方向，注：也就是和多邊形內(nèi)環(huán)相反的方向）采用其第(n–3)個子節(jié)點將采用的形式：(m–1)|mrot???(p)。（注：任意一個多邊形頂點(2-cycle)中都有且僅有一個不參與融合的1-cycle）

• 所有其他的頂點要么是葉子（它們沒有子節(jié)點），要么正好有(n-3)個子節(jié)點。

• 當一個分支中的頂點的level（等級，可以理解為到多邊形的路程）L達到其自身和所有非根祖先的min{Lj+?j-1}（注：(Lj+?j-1)的最小值）時，它就變成了一片葉子，其中Lj是這些頂點的levels，?j是它們相對于父節(jié)點的旋轉(zhuǎn)。所以?=1的每個頂點都是一片葉子，而樹的每個節(jié)點上旋轉(zhuǎn)最大的頂點，將受到根的子節(jié)點(n-4)的最大值L的限制，即在根之后總共有(n-4)代。

這棵樹中的子節(jié)點和父節(jié)點在他們的2-cycles之間有單個的交集（注：一個公共的1-cycle）是正確的構(gòu)造，因此，要確認圖形始終由根位于(n–1)-多邊形頂點的(n–1)樹組成，相當于檢查除我們描述的邊之外沒有其他邊。

在我們版本的Williams（威廉姆斯）結(jié)構(gòu)中，有(n-1)(n-3)!形式為m|nrq的2-cycles，其中(r,m)是(1,2),(2,3),…,(n-2,n-1),(n-1,1),中的(n-1)個選擇之一，q是剩余數(shù)字的任何排列。我們將稍微濫用符號并寫成r=m-1，并隱含從1到(n-1)的循環(huán)的包裝（注：也就是1-1當成(n-1)），所以我們可以寫成m|n(m-1)q。

對于要融合的兩個2-cycles，它們必須以不同的m值開始，因此假設(shè)我們有m?|n(m?–1)q?和m?|n(m?–1)q?，其中m?≠m?。由于m和(m–1)永遠不等于n，我們有以下幾種可能性（注：這似乎是上面構(gòu)造法的原理）：

• m?=m?–1。那么m?≠m?–1，所以它一定是q?的數(shù)字之一。假設(shè)q?=am?b；那么這兩個2-cycles可以寫成：

  m?|(m?–1)q?n

  (m?–1)|m?bn(m?–2)a

  使用我們的2-cycle交集規(guī)則，當且僅當bn(m?–2)a和q?n是相同的模的旋轉(zhuǎn)（注：有效旋轉(zhuǎn)位數(shù)=旋轉(zhuǎn)位數(shù)mod旋轉(zhuǎn)周期）時，i.e.當q?=(m?–2)ab時，將有一個單一的交集。這意味著我們的2-cycles的形式為：

  m?|(m?–1)(m?–2)abn
  (m?–1)|m?bn(m?–2)a

  第一個是我們上面描述的樹中的父節(jié)點的形式，m|(m–1)p，如果我們把m=m?和p=(m?–2)abn放在一起，第二個則是它的???（第?個）子節(jié)點，(m-1)|mrot(p)，是?=1+|a|（注：Len(a)，下同）的位置。請注意|a|+|b|=n–4，因此?的范圍是從1到(n–3)。

  ?○?假設(shè)(m?-1)(m?-2)abn在循環(huán)上等價于序列(n-1)…321，其中n替換m?。然后父節(jié)點是(n–1)個根節(jié)點之一，這些根節(jié)點是中心多邊形的頂點。當|b|=0時，子節(jié)點也只能是多邊形中的一個頂點，因為否則b中最右邊的數(shù)字上會有兩個相互矛盾的條件：父節(jié)點需要對應(yīng)于(m?+1)才能成為根節(jié)點，而子節(jié)點需要對應(yīng)于m?才能成為根節(jié)點。但是|b|=0對應(yīng)于|a|=n–4和?=n–3，這正是我們描述的多邊形中相鄰頂點為父節(jié)點和子節(jié)點的條件。

  ?○?如果我們修復(fù)這對中的子節(jié)點2-cycle，那么也將修復(fù)父節(jié)點。因此，這種形式的每個子節(jié)點都有一個唯一的父節(jié)點，其m值大1（通常在(n–1)處返回到1），我們需要證明，在m值重復(fù)之前，重復(fù)使用唯一的父節(jié)點將使我們返回到一個多邊形頂點，我們有機會在2-cycle圖中形成一個循環(huán)。假設(shè)我們從一個不是多邊形頂點的子節(jié)點開始，這樣m?bn(m?–2)a就不是在循環(huán)上等價于序列(n–1)…321了，其中用n替換(m?–1)。我們將刪除下標，只需將從子節(jié)點到父節(jié)點的映射編寫為：

  (m–1)|n(m–2)amb→
  m|n(m–1)(m–2)ab

  換句話說：如果我們在"|"的左邊有(m–1)，并且我們寫了從n開始的右邊部分，我們從右邊部分提取m并將其放在左邊，然后在右邊的n后面放(m–1)。如果我們繼續(xù)此過程，并使用一系列修改過的字符串a'etc.來保持統(tǒng)一的模式，我們有：

  (m–1)|n(m–2)amb→

  m|n(m–1)(m–2)a'(m+1)b'→

  (m+1)|nm(m–1)(m–2)a''(m+2)b''→

  (m+2)|n(m+1)m(m–1)(m–2)a'''(m+3)b'''→...

  因此，無論原始的a和b是什么，最初版本的組合長度在每一步減少1，在最多(n–4)步之后，我們最終精確地得到根節(jié)點的下降序列。

• m?≠m?–1。那么m?必須是q?的數(shù)字之一，并且為了不簡單地在索引交換的情況下重復(fù)前面的情況，我們還必須要求m?≠m?–1。因此，在我們在(n?–1)處換行的通常循環(huán)排列中，m?和m?必須相差1以上。所以我們的兩個2-cycles將是以下形式：

  m?|n(m?–1)a?m2b?
  m?|n(m?–1)a?m1b?

  或者，如果我們將它們旋轉(zhuǎn)成合適的形狀以檢查交叉點：

  m?|m?b?n(m?–1)a?
  m?|m?b?n(m?–1)a?

  但這兩個循環(huán)永遠不會相交，因為在這兩種情況下，n右邊的不同數(shù)字意味著b?n(m?–1)a?和b?n(m?–1)a?永遠不會是相同的模的旋轉(zhuǎn)。（引用結(jié)束）

? ? ? ? 最后任選多邊形上兩個相鄰的頂點（兩個2-cycles），找到兩個2-cycles的公共1-cycle。融合前，在“公共但不完全公共（排列順序不一樣）”的兩個1-cycles中任選一個，把選的這一個1-cycle的開始排列叫做u，結(jié)束排列叫做v，v沿著?到達的排列叫做s，最后按照之前圖片中的方法，完成超排列。

*如果你想證明擁有公共1-cycle的任意兩個2-cycles可以融合，可以把公共1-cycle分成四截字符串，做到四個端點接著四截不同的字符串就行了。

(? ?E?? N?? D? ?)