上一篇专栏的证明过程确实有很多的bug，所以这次来个二周目。（这样我就可以再水一篇专栏了٩(๑^o^๑)۶）

*文中带删除线的地方对于各位学术巨佬可能是废话，可以自行跳过。如果对不带删除线的内容有不理解的地方，可以看一下这些内容。

        首先，让我解释一下cv11662452中的一种超排列递推构造方法的原理，这个原理是我在研究所的厕所中想到的，至今还没有人正式发布过∠( ᐛ 」∠)＿。（构造法 http://www.notatt.com/permutations.pdf ）

        先回顾下这个构造过程▽

        n=0时，0个元素的全排列只有“”，而超排列“”就包含了这个全排列，长度为0，不能再短了（长度不能是负数）。

        经过众多院士和计算机的不懈努力下，证明出n=1时，最短超排列就是“1”，长度为1。（“1”的全排列只有“1”，而超排列“1”就包含了这个全排列，长度为1，长度为0的数字串无法包含这个全排列，不能成为超排列，所以……）

        以此为基础构造出n>1的超排列。（不一定最短）

        构造方法：从左往右看，按出现的顺序依次列出(n-1)的所有的全排列（把初始超排列“拆开”），并且每个排列连续列两遍（像“abc”->“aabbcc”这样）。最后在每组相同的排列间插入数字“n”（像“aabbcc”->“adabdbcdc”这样）并把相邻的不同排列之间重复的部分删去（这个步骤相当于是“拆开”的逆向过程）。

        这是一个从一个有2种符号的超排列中创建一个有3种符号的超排列的图。

        知道了构造方法后，就可以开始构造了٩(๑^o^๑)۶

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

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

“121”->“123121321”↓

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

|(⁄ ⁄•⁄ω⁄•⁄ ⁄)厂⁽˙³˙⁾                                      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   :

|⁽˙³˙⁾◟(๑•́ ₃ •̀๑)◞⁽˙³˙⁾                       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   ³   12 _ 21   ³   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种符号的以这种构造方式构造的超排列的长度。通过简单的分析可以得出

*通过(n-1)(n≥2)种字符的超排列构造n种字符的超排列，这个过程相当于原本拆开产生的数又在拼接时去除，数的个数不变。而在两者之间，复制出了(n-1)!个1到(n-1)的排列，每个排列有(n-1)个数此外还有添加的(n-1)!个数字n，所以多出数字的总个数就是：

        然后用口算就能得出。

        看到这里你可能满脑袋问号？？？？？

        这个过程为什么可以构造超排列？

        为什么这个过程不会出现bug？

        好的，现在我就来解释这个构造方法的原理▽（和BV14f4y137LU的玉米拼图解法相似）

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

1.先列出1到(n-1)的所有排列（每个列两遍），然后在每两个相同排列之间加上数字n。

2.像节目[The Price Is Right]这样（其实和超排列的规则相似）

        从左到右依次取n个连续的数字，你会发现n个1到n的排列。

        对每个（共(n-1)!个）排列都这样做，就能得到(n-1)!×n=n!个不同的排列，也就是1到n的全排列。（因为框框必须包含数字n，又因为“拼接”和“拆开”是对称操作，不涉及数字n，而且“拼接”后每个n两边的排列不变，所以在“拼接”过程中不会产生重复的排列也不会“损失”排列，进而得知构造1到(n+1)的排列时第一步没有bug）

*如果框框的位置不同，那么排列一定不同，因为数字n的位置不同。

*如果数字n两边的1到(n-1)的排列不同，那么排列也一定不同，因为如果排列相同，那么把它们所在的框框分别移到最左边（右边）所得到的排列一定相同，即数字n左边（右边）的1到(n-1)的排列相同。（把框框移到左边〔右边〕相当于把框框内数字n右边〔左边〕的部分Ctrl+X（"X"代表剪刀）再Ctrl+V（"Viscidity"（粘性的））到框框左边〔右边〕，要么都不是〔〕中的内容，要么都是〔〕中的内容）

        1到n的全排列是有了，那“拼接”会不会有问题呢？

        不会，由于每个数字n两边的排列不同，所以不能把数字n拼在一起，不然两边的排列对不上不能拼，因为排列的每个数字只出现一次，过了这个村就没这个店，没过这个村也没这个店，多“拼”少“拼”都不行，除非你不“拼”（这样的构造法明显不划算）。至于其它阴间的拼法就不深入讨论了。可以但没必要，只是为了构造。

        所以只要按“拆开”的反向操作“拼接”就行（“拆开”时每个排列都要与两边的排列分离，而“拼接”只要和一边接在一起就行了，显然没问题）

        好了，这种构造法就解释完了。（之后不再讨论n=0的情况，因为确实没有必要）

        4chan的网友（大佬）得出的凉宫春日问题下界（目前已知最大的下界）是这个

        接下来我就用深入浅出的方法来解释这个下界的由来。

        这用的是 https://oeis.org/A180632/a180632.pdf 的推导过程，而该论文又出自 https://mathsci.fandom.com/wiki/The_Haruhi_Problem （该网站还引入了两个简单下限的证明，这两个下限是和）

        现在我给出这两个简单下界的证明过程（会数数的人应该都看得懂）

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

        先从n种字符中取下一个字符放在序列的开头，一共有n种选法，然后在剩下的(n-1)字符中再取下一个字符放在序列的第二个位置，一共有(n-1)种选法，一直到最后一个字符都取下并放入序列为止。根据分步乘法计数原理得，总方法数是从1到n的所有整数的积，即n!（n的阶乘）。（“按某种顺序依次取下字符并选一个序列的空位放入”的方法也是可以的，但是不能以“任取字符放入任选位置”这样的方法分析，因为这样计数会有重复）

        于是，n种字符的全排列有n!种。为了完成超排列，就必须把这些排列排列（可以删去重复部分），任选一个排列放在序列的开头，之后若要引入新的排列，至少得添加一个字符（当第一个排列的最后(n-1)个字符和添加的第一个字符连成一个新的排列时，就可以只添加一个字符）。因为每种排列都是不一样的，所以必须通过添加字符来引入新的排列。那么添加剩下的(n!-1)个排列就至少添加个字符（最好每次添加一个字符就引入一个新的排列，就可以只添加(n!-1)个字符）。

        显然，当n较大时，只添加(n!-1)个字符是不可能完成超排列的，因为“通过添加一个字符引入一个排列”的方法只有把上一个排列的第一个字符Ctrl+C（"Copy"）&Ctrl+V到最后（因为一个排列中没有重复的字符）。不难发现，“加一个字符就引入一个新排列”这样的事件不可能连续发生n次，即使连续发生(n-1)次，第n次也一定不会发生。

        要想完成超排列，就得从某个初始排列开始，引入(n!-1)个新排列，因为上述结论，所以最理想的办法可以是先进行(n-1)次“加一个字符并引入一个新排列”再进行一次“加两个字符并引入有且仅有一个的新排列”，一直重复到所有排列都出现为止。此时“加两个字符并引入一个新排列”的事件的次数是[(n!-1)÷n=(n-1)!-1…n-1]次（n=1时，事件的次数是0次，规定0!=1，把n=1代入该余数除法算式，得"0÷1=0…0"，确实是0次，这体现了规定0!=1的好处），所以“加一个字符并引入一个新排列”的事件的次数自然就是次，算上初始排列的长度n，就可以得出一个更好的下限，即

*我认为这样算更快—>（添加字符的总次数加上添加两个字符的次数，添加一个字符的次数只计入一次，而添加两个字符的次数计入了两次）。

接下来介绍 https://mathsci.fandom.com/wiki/The_Haruhi_Problem 对两个简单下界的证明↓

        他定义了这样几个量↓

L:字符串的实时长度（字符个数）

N₀:字符串中不同排列的实时个数

令X₀=L-N₀

X₀一开始就是(n-1)（第一个排列的长度n减去排列的个数1），N₀+1（引入一个新排列），L必须至少+1（必须添加字符才能引入新的排列）。

        所以随着字符串的加长，ΔL≥ΔN₀，ΔX₀≥0，于是X₀≥n-1。所以，当超排列完成时，

        我们在幼儿园就……坐过圆桌。和之前一样，n个小朋友坐有n个座位（每个座位都不一样）的圆桌有n!种坐法。如果只考虑小朋友之间的相对位置，那么一共有几种坐法呢？考虑其中一种坐法，以任意一名小朋友为起点，按顺时针方向给小朋友排队，因为有n个小朋友，所以有n种排法，也就是说这个问题的一种坐法对应了n个小朋友排队的n种排法，而n个小朋友排队共有n!种排法，所以该问题的答案乘以n等于n!，得出该问题的答案是(n-1)!（在0!=1的规定下，n=1时仍成立）。

        n种字符的圆排列数是(n-1)!（n=1时仍成立，下同），所以我们可以把n种字符的n!种排列分成(n-1)!堆，每堆（在上述网站中被称做"1-loop"）都有n个对应一种圆排列的排列，这时定义N₁为包含已引入的排列的堆的个数。

        从某一堆的某个排列开始，只添加一个字符，要么引入这个堆中的排列（把这个排列的第一个字符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种字符的圆排列数）。也就是说，因为必须引入(n-1)!个堆的所有排列，所以当超排列完成时，

        我忍不住了，所以决定在解释最后的下限之前，先补充下 https://mathsci.fandom.com/wiki/The_Haruhi_Problem 网页中的一些概念：（和图论相似）

        可以把超排列想象成一个有向图，每个排列是一个节点，连接节点的“箭头”是排列间的转换过程（把某个排列的前若干个字符Ctrl+X&（选中的字符串的字符，下同）调整顺序&Ctrl+V到后面，并尽量减少剪切字符个数）。尽量用最少的字符引入一个新排列，这对其他“箭头”是没有影响的（可以参考上文对超排列递推构造法过程的解释，或者这样理解：某个“箭头”“长度”（剪切字符个数）变化，但两端的节点（排列）是不变的，也就是说，前一个“箭头”的终点和后一个“箭头”的起点不变，同样地，其他“箭头”也不变），这样只会减少L，所以是合理的，也就是说“箭头”是唯一的（取最短），如果过程中引入了其他排列，即“箭头”“穿过”了其他节点，则把这个过程分成多个过程，也就是把“箭头”沿节点“断开”，这样只会引入更多的排列并可能减少L，所以它是合理的。

1-edg(EDGNB)e相似于最简单的“箭头”，它指的是，通过把某个排列的第一个字符Ctrl+C&Ctrl+V到最后来引入一个排列。

2-edge是指通过把某个排列的前两个字符Ctrl+C&调换顺序&Ctrl+V到最后来引入一个排列。（如果不调换顺序的话就等效于两个1-edges了，没有意义）

x-edge是指通过把某个排列的前x个字符Ctrl+C&调整顺序&Ctrl+V到最后来引入一个排列（可以分解成若干个小edges的x-edges除外），下文中的x-edge是指通过把某个排列的前x个字符Ctrl+C&倒序（ABC->CBA）&Ctrl+V到最后来引入一个排列，可以把它看作“狭义的x-edge”。

1-loop（使排列成环，无始无终，下同）是指一些对应着同一个圆排列的n个排列的集合，n种字符一共有(n-1)!种圆排列，所以就有(n-1)!个1-loops，如果引入了一个1-loop中的所有排列，就算完成了一个1-cycle（有始有终，下同）。（ https://zhuanlan.zhihu.com/p/150582767 中解释了loop和cycle的区别，部分资料没有对这两者有明显的区分，所以不必太计较）

2-loop是指“任取一个n种字符的排列，作(n-1)次1-edges，再作一次2-edge，重复这两个过程（不能调换顺序），经过的所有排列的”集合。（2-cycle是啥不用我多说了）

x(x≥3)-loop(cycle)目前还没有明确的定义，x-loop和x-cycle（可以把它看作“狭义的x-loop(cycle)”）会在下文做解释。

        下图解释了为什么一个2-cycle(loop)有n(n-1)个排列。

        现在介绍一下这个网站对第三种下限的证明(n≥2)：

为了在某个过程中的N₁+1，必须得完成一个1-cycle，并进入一个新的1-cycle。（周而复始）假设起点排列是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的话，在出发点P之前一定引入过P①（不然就违反了该网站的默认规则），所以上一步到达P（已引入）时N₀+0。（由于P已引入，所以“上一步”是存在的）除①外，还有两种进入新的2-cycle的方法②③。通过x(x≥3)-edge②或者通过2-edge使N₁+0③。（这三种方法互斥但不一定可行，但包括了所有进入新的2-cycle的方法）

        最后，定义N₂为进入2-cycle的个数（像上上上图中的2-loop，规定通过非1-edge引入的“蓝色排列”时N₂+1，同时该“蓝色排列”相应的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，结合这两步，Δ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之间没有公共排列时取"="），所以当超排列完成时匿名网友的证明结束了。（不难发现，只有N₀+1，N₁才可能+1，只有N₁+1，N₂才可能+1）

        我在 https://b23.tv/c9Dl9y 和 https://b23.tv/mQuy2f 上发布了Robin Houston发布的对4chan网友的证明过程改进后的证明过程(n≥2)。

        当时对2-loop没有一个清楚的认知，所以各位在看“wt(πₘ，πₘ₊₁)=2的情况”时可能会有“为什么一定要严格按照2-cycle的路径走？”“这样也算在一个2-cycle中的话，那v能达到(n-2)!吗？”等疑惑。看完了上述的证明过程，这些疑惑自然就解决了，把πₘ看做P，把σ看做P'，σ和πₘ₊₁都在从σ开始（σ不一定就是这当中第一个被引入的排列）的2-loop，它们都可以看做这个2-loop中的两个“蓝色排列”，这个2-loop中的(n-1)个“蓝色排列”都有机会使v（N₂）+1。因为每个2-loop由(n-1)个1-loops构成，想要完成超排列，就得引入所有的排列，就得进入所有的1-cycles（(n-1)!个），就得至少进入(n-1)!/(n-1)=(n-2)!(n≥2)个2-loops。所以最终v≥(n-2)!。（现在各位再返回去看证明过程应该就能理解了）

        在Robin Houston的证明过程中，把c(π₁,…,πₘ)定义为π₁,…,πₘ₋₁过程中完成的1-cycle的个数，这样就避免了匿名网友证明过程中出现的“上一个”。但大致思路是一样的，都是“从一个一个小过程推导到整个过程”。

        此外，在匿名网友的证明过程中，还提了一句“贪婪的圆环算法使用越来越大的循环：它通过(k+1)-edge连接(n-k)个k-loops，以制作(k+1)-loops。但我还没有能够证明这些更大的循环”。（此处暗红色加粗部分应该没问题）

        于是……

        “看起来胜利在望！感觉只要我们花足够多的时间，足够努力去打磨这个方法，我们最终总能证明，超排列的长度至少是，从而证明这个猜想。事实上，当时每一个了解这个问题的数学家，都确信猜想成立。当时有人在MathOverFlow上问这个问题，回答者们甚至都开始讨论起输出超排列的序列的算法了。这个问题甚至还出现在了1998年的土耳其信息学竞赛里。看起来计算机学家们已经默认我们构造出的序列就是超排列了，他们开始关心如何更快的输出这个序列了。当时很多数学家都在怀疑，这个猜想到底是不是真正‘的未解决的数学问题’，还是只是大家懒得去花时间写下这个人人都认为成立并且简单的证明。”—— https://www.zhihu.com/answer/532606339 

        等一下，各位有没有发现，这个（第二种构造法）“最短”长度和之前构造法（第一种构造法）长度是一样的，其实两种方式构造的超排列可以是一样的。（我们认定第二种构造方法如下下图，构造(n-1)-cycle（看上图就知道为啥是(n-1)-cycle了），即“为了不断地引入新排列，在超排列完成之前，1-edge用不了（无法引入新排列，下同）就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”的构造，即尽量用短的x-edge，看下下图就知道了）

        n较小时，一眼就能看出这一点（两种方式构造的超排列可以是一样的），而且这种超排列的构造可以理解为“为了不断地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”的方式。而第一种方法的递推过程，可以看做把每个edge都加长1，并把每个排列都变成相应的1-cycle（可以理解为“0-edge（？）变成1-edge”）”的过程，所以递推后“为了不断地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”这样的方式仍然适用，用数学归纳法的思路，得出第一种构造方式就是“为了不断地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”。不难发现，“为了不断地引入新排列，在超排列完成之前，1-edge用不了就用2-edge，2-edge用不了就用3-edge，……，x-edge用不了就用(x+1)-edge”这样的方式就是构造(n-1)-cycle的方式，也就是第二种构造方式！

        在 https://www.zhihu.com/answer/532606339 的鼓励下，我给出了新的下限证明如下：

如果超排列的1,2,3-edges都是按下图这种规则构造会最短的话，那么3-edge只有一种，就是下图的红色箭头这种，因为其他5种都不行，要么等价于1-edge或2-edge，要么会在第二个2-cycle重复（不信的话你可以试试看或看下下图）。

        那么3-loop的定义也明确了，用之前的方法就可以证明。（可惜加粗部分我不能证明），直到我看到 http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_nsk666646664466646666_2SYMM_FS.txt （这个网址的"666646…"好像是该超排列中连续的1-edge数目，但又仿佛不是……），罗宾·休斯顿（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 的话，有删节）

        为了保持以非传统方式宣布超排列的传统，马特·帕克（Matt Parker）提出在他的一次活动中让一架自弹钢琴演奏这首歌（长度是5906的n=7的超排列）来“发表”这首歌。因此，如果你想亲自聆听这种以七音音阶（因为n=7）呈现的超排列，这里有几个MIDI版本音乐可供选择：

C小调，钟琴→ http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_C_Minor_Glockenspiel.mid 

降B大调，钟琴→ http://www.gregegan.net/SCIENCE/Superpermutations/7_5906_B_Flat_Major_Glockenspiel.mid 

C小调，钢琴→ 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 

        这个超排列是如何发现的？先来点背景故事。自从罗宾·休斯顿（Robin Houston）通过旅行商解算器找到了n=6的最短超排列（下面有论文PDF链接）后，他和几位合作者一直在试图理解和推广该超排列的结构（以及他后来发现的数千个相同长度的超排列）

        直到最近，这里的最新技术是从相同n值的标准超排列（通过上文的递归构造法构造的排列）的一部分开始，包括许多完整的3-cycles（此处暗红色加粗应该没问题，下同）。每个3-cycle是由edges of weight 3(也许是3-edges)连接的（n–2）个2-cycles的序列，（之前讲过）而连续的3-cycle通过edges of weight 4(也许是4-edges)相互连接。通过获取该初始“内核”，然后将其与连续的2-cycles合并，可以访问每个置换，至少对于n=6和n=7，总长度为：

        此前，在2019年2月1日，"查理·维恩（Charlie Vane）"发现了一个n=7情况下长度是5907的超排列，（在当时）是一个新的记录！这是在马特·帕克（Matt Parker）在YouTube上关于超排列的视频 https://www.youtube.com/watch?v=OZzIvl1tbPo&lc=UgzxhVwUBG9EyyldHGd4AaABAg.8qeg_FoKqzY8qmPR3OErzH 的评论区宣布的。

        n=7，5907位数字，由"查理·维恩（Charlie Vane）"发现( http://www.gregegan.net/SCIENCE/Superpermutations/7_5907_CharlieVane.txt )

        显然， "查理 · 范恩" 是博格丹 · 科安达（Bogdan Coanda）的网名， 他提供了如何找到这种超级排列的解释 https://groups.google.com/d/msg/superpermutators/KNhmzQy99ic/obl6pCt5HwAJ 。

        （引用结束）

 【【Numberphile】超级排列数 @圆桌字幕组-哔哩哔哩】【视频标记点 05:19】https://b23.tv/JJXWEu （在QQ和微信等通讯平台发送它并点击链接可以直接到达时间坐标，或单击05:19进入视频）

        接下来就到了最难的部分——最新上界（科幻作家及数学家格雷格·伊根（Greg Egan） 通过https://arxiv.org/pdf/1408.5108.pdf ，得知1≤n≤6时最好的上限不是这个，之后他才在网站的后面补充了长度是5906的n=7的超排列，但他好像忘把这个上限的n的范围改成(n≥8)了）的证明。

        参考 http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html 的证明过程，这是Greg Egan在2018年10月提出的，他参考了Aaron Williams在2013年设计的结构。

        稍微总结一下↓（再引用 http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html 的话）

（Greg Egan）通过调整 Aaron Williams（论文PDF https://arxiv.org/pdf/1307.2549.pdf ，各位量力而行） 在 2013 年设计的结构，可以生成的超排列的长度是：（比之前的递推构造好）

……

比标准算法或这种新构造产生的超排列更短的超排列目前仅在两种特定情况下（前提是n≥6）为人所知：

• 对于n = 6，如前所述，Robin Houston 使用解决旅行商问题的算法发现了长度为 872 的超排列，此后他设计了新方法，产生了数千个这种长度的示例。

• 对于n = 7，Bogdan Coanda 开发了一种更快的算法，该算法发现了几个长度为 5907 的超排列。随后，休斯顿进一步完善了他的想法，在他的帮助下，我（Greg Egan）能够将两种方法结合起来，找到几十个 长度为 5906 的超排列。

        如果我们找到一种构造这种长度的排列的方法（Greg Egan提出的每种排列只经过一次的构造，之前提到过），那上界就不证自明了，然后我看到了这句话：

“为了使 Aaron Williams 在通过对称群的哈密顿路径上的工作适应构造超置换的问题，我们需要缩减图，使它们只包含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（删去被复制的1个字符）”，把 δ （排列变换操作）定义为“2-edge（删去被复制的2个字符）”。Aaron Williams对 σ 的定义和Greg Egan的一样，但是他没有定义 δ ，而是像上面这句英文这样，即把 τ （排列变换操作）定义为“把最排列前面的两个字符调换顺序”。但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.（翻译：好消息是，威廉姆斯选择排列所做的大部分优美的工作，可以毫不费力地改编，用我们的 σ 和 δ 来代替。）但我不能理解他为啥这么说，我也没有看到相关文献，所以我思考了一下，想出了用 σ 和 δ 代替 τ 的方法：对于n种字符的一个排列（以123...n为例，其他同理），先用1次2-edge，把排列变成3...n21，再用(n-2)次1-edge把前(n-2)个字符放到最后，排列变成213...n，这样就成功地把前两个字符交换顺序了，也就实现了 τ 。但是他又提出：It turns out that these two permutations are enough to generate the whole group（事实证明，这两种排列足以生成整个组）。后来我理解了，就像下面这个图一样，用1-edges确定交换字符的位置（像下图的隔板一样），再用 τ 交换字符，最后用1-edges把隔板“复位”就可以交换任意两个相邻字符的位置（也可以不“复位”，方便下一次交换）。像冒泡排序那样反复操作，就可以变成任意一个排列了。

        作者用 δ 和 σ⁻¹ （把某排列的最后一个字符Ctrl+X&Ctrl+V到排列的最前面，和“倒着的1-edge”类似）构造alternating cycle（可以看做在几个1-cycles间反复“交替”横跳，）。

*对于任意一个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一一对应。

        取(n–1)对循环连续数字(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)对应(n-3)!种q，一共有(n–1)(n–3)!种"mnrq（此处省略字符或字符串的连接符，下同）"型排列，并列出以这些"mnrq"型排列为起点的alternating cycles。从上图的每一个alternating cycle可以看出，1(m)只会左右横跳，剩下(n-1)种字符连成排列就像1-loop一样。（*"~"表示连续的递增的数字，如果"~"两端的数字相等则合并，若"~"前的数字比"~"后的大1，则删去"~"及两端。123~n→ δ →3~n21→ σ⁻¹ →13~n2→ δ →4~n231→ σ⁻¹ →14~n23→…，1在左右横跳，加粗部分可以用 σ 连接）要么m在不同的位置，要么剩下(n-1)种字符连成排列不同，要么两个都不同，总之在任何一个alternating cycle里找到相同的排列。

        看下方n=4的示意图，这些以这些"mnrq"型排列为起点的alternating cycles没有重复的排列，而这一点是可以证明的↓   当几个起点的m和r相同时，因为q不同，所以对于从任意的几个这样的起点开始的alternating cycles分别选出的排列，即使m在同一侧，剩下(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在相同位置，相应的r₁和r₂也不同。（就算通过"rot"使n在倒数第二位，就算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!个排列连成环，所以一共有n!个edges，其中有(n–1)²(n–3)!个2-edges（有(n–1)(n–3)!种alternating cycles，每种alternating cycle有(n-1)个2-edges），那剩下就有[n!-(n–1)²(n–3)!]个1-edges。所以edges的总长度是（可以用总edges的个数n!加2-edges的个数[n!-(n–1)²(n–3)!]）        Aaron Williams找到了一种方法，可以把所有的排列连成两个大环（想象一下把所有排列做成珍珠，再把珍珠分成两堆分别串成两个项链），然后按下图把两个大环做成一个超排列。

        所以最终的上限是

THE END

        诶，是不是还少了什么，Aaron Williams发现的这两个大环是怎么形成的？还有，为啥它们可以这样拼在一起？Greg Egan网站的几个图片似乎提供了答案。

        *这几幅图的每一个节点是一个2-cycle，但不一定是以"mnrq"型排列为起点的alternating cycles对应的2-cycle。

*这五幅图中的m|q（m是一个字符，q是一个字符串，注意区分mnrq和mq）是2-cycles的一种表示方式，它表示以某个"mq"型排列为起点的alternating cycle对应的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都对应一个2-loop，第一幅图形象演示了两个2-cycles（该图中左边那个2-cycle就是左上方这个2-cycle）合并的过程（两个相同的1-loops合并），按照这样的规则，可以把n=4情况下的三个2-cycles合成两个一大一小的环。

        第二、三幅图分别是n=6和n=7的图。第四幅图的阴影部分内边界和外边界分别对应两个环，一个在正多边形内，还有一个由“沿着树枝的表皮爬行”得到。第五幅图是最新的研究进展图，显示了8棵2-cycles树，它们附着在内核（上文提过）上以产生超置换，您别说这个图还有点上下对称的感觉。（节点的颜色由"|"前的数字决定，第二、三、四，的节点颜色的波长随"|"前的数字的增加而减小，多边形内部循环是逆时针进行的）

        接下来，考虑n≥4的情况。

*接下来的内容会有一点点难，建议小孩和不懂事的大人在家人的陪同下食用。

        先给出多边形（内部）循环的构造方法：

想找到这个循环，可能需要构造一种排列，步骤以及e.x.如下↓

1. 在rot((n-1)~1)输出的(n-1)个排列中，任选一种。

2. 在选中的排列的第一和第二个字符中间插入字符n，得到一个有n种字符的排列。

3. 因为步骤1.有(n-1)种选法，所以经过步骤2.得到的排列也有(n-1)种。

4. 比如n=6，步骤1.的输出是54321,43215,32154,21543,15432，经过步骤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。

*"~"表示连续的递减的数字，如果"~"两端的数字相等则合并，若"~"前的数字"~"比后的小1，则删去"~"及两端。

        对于2-cycle 2|n1(n-1)~3，从2n1(n-1)~3开始。沿2-cycle彳亍走，得（děi）先执行 δ （原因见上，下同），得1(n-1)~3n2，接着执行(n-3)次 σ ，得3n21(n-1)~4。和之前一样，在得到的排列的第一个字符后加上"|"，就发现（没发现的可以看看之前的步骤）这是之前说的(n-1)个2-cycles中的一个，即3|n21(n-1)~4，可以看做是进入了下一个2-cycle（除n以外的字符都变成了和自己相邻的下一个字符。特别地，(n-1)的相邻的下一个字符是1，下同）。一直重复这个过程（遍历了这(n-1)个2-cycles），你会发现，按照上上图中提到的对称性，除n以外的字符都在以相同的规律变化着。在这个过程中，遍历的这(n-1)个2-cycles可以串在一起。自然地，既然能从这(n-1)个2-cycles中的一个2-cycle进入了“下一个2-cycle”（参考上文，下同），那么这两个2-cycles就可以融合，而上文的“执行(n-3)次 σ ”的过程其实就是沿这两个2-cycles的公共1-cycle彳亍走。这(n-1)个2-cycles中的每一个2-cycle都和“下一个2-cycle”融合，(n-1)次融合后，一个“多边形”就生成了。相应地，“多边形”内部的这个较小的环也找到了，参考上文orange部分（经过这(n-1)个2-cycles）。换个角度想，你可以先找出这个较小的环，它遍历的2-cycles，就是这(n-1)个2-cycles。

*Greg Egan构建多边形顶点和构建附加树的规则相当简单。

        Greg Egan给出的(n-1)个2-cycles（我的2-cycles"|"后的字符串调整一下就是他的）：

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

再给出外面的大环——“以多边形为根生长的树枝”——的作者的构造法（节点就是2-cycle）（有删节）：

*树状图是一种数据结构，若节点A往远离多边形的方向移动一节到节点B，则把节点A叫做父节点，把节点B叫做子节点。还存在其他使用“父（子）节点”这两个词的情况，见下文

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

*特别规定1-1就是(n-1)，此处的减法和一般的减法不一样，它表示沿循环逆向移动，此处的加法也同理

*下面的有些引理没有证明，下面这个只能算是终极结论的证明思路，不过我相信各位可以自行证明这些引理，如果不会的话请评论或私信

• 每个子顶点的m值都比其父节点小1（特别地，父节点的m=1时，子节点的m=n–1）

• 如果我们将父节点写为m|(m–1)p，那么它的子节点是(m–1)|mrot(p)，其中rot是向左旋转ℓ个位置（注：执行ℓ次 σ ），ℓ的范围是从1到n–3。（注：如果各位想要证明子节点的表示法，可以把p分成两截，左边那截长度为ℓ）

• 每个根节点（注：多边形上的节点，可以理解成父节点）恰好有(n–4)个子节点，多边形中的一个邻居（图中是顺时针方向，注：也就是和多边形内环相反的方向）采用其第(n–3)个子节点将采用的形式：(m–1)|mrotₙ₋₃(p)。（注：任意一个多边形顶点(2-cycle)中都有且仅有一个不参与融合的1-cycle）

• 所有其他的顶点要么是叶子（它们没有子节点），要么正好有(n-3)个子节点。

• 当一个分支中的顶点的level（等级，可以理解为到多边形的路程）L达到其自身和所有非根祖先的min{Lj+ℓj-1}（注：(Lj+ℓj-1)的最小值）时，它就变成了一片叶子，其中Lj是这些顶点的levels，ℓj是它们相对于父节点的旋转。所以ℓ=1的每个顶点都是一片叶子，而树的每个节点上旋转最大的顶点，将受到根的子节点(n-4)的最大值L的限制，即在根之后总共有(n-4)代。

这棵树中的子节点和父节点在他们的2-cycles之间有单个的交集（注：一个公共的1-cycle）是正确的构造，因此，要确认图形始终由根位于(n–1)-多边形顶点的(n–1)树组成，相当于检查除我们描述的边之外没有其他边。

在我们版本的Williams（威廉姆斯）结构中，有(n-1)(n-3)!形式为m|nrq的2-cycles，其中(r,m)是(1,2),(2,3),…,(n-2,n-1),(n-1,1),中的(n-1)个选择之一，q是剩余数字的任何排列。我们将稍微滥用符号并写成r=m-1，并隐含从1到(n-1)的循环的包装（注：也就是1-1当成(n-1)），所以我们可以写成m|n(m-1)q。

对于要融合的两个2-cycles，它们必须以不同的m值开始，因此假设我们有m₁|n(m₁–1)q₁和m₂|n(m₂–1)q₂，其中m₁≠m₂。由于m和(m–1)永远不等于n，我们有以下几种可能性（注：这似乎是上面构造法的原理）：

• m₁=m₂–1。那么m₂≠m₁–1，所以它一定是q₁的数字之一。假设q₁=am₂b；那么这两个2-cycles可以写成：

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

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

  使用我们的2-cycle交集规则，当且仅当bn(m₂–2)a和q₂n是相同的模的旋转（注：有效旋转位数=旋转位数mod旋转周期）时，i.e.当q₂=(m₂–2)ab时，将有一个单一的交集。这意味着我们的2-cycles的形式为：

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

  第一个是我们上面描述的树中的父节点的形式，m|(m–1)p，如果我们把m=m₂和p=(m₂–2)abn放在一起，第二个则是它的ℓᵗʰ（第ℓ个）子节点，(m-1)|mrot(p)，是ℓ=1+|a|（注：Len(a)，下同）的位置。请注意|a|+|b|=n–4，因此ℓ的范围是从1到(n–3)。

   ○ 假设(m₂-1)(m₂-2)abn在循环上等价于序列(n-1)…321，其中n替换m₂。然后父节点是(n–1)个根节点之一，这些根节点是中心多边形的顶点。当|b|=0时，子节点也只能是多边形中的一个顶点，因为否则b中最右边的数字上会有两个相互矛盾的条件：父节点需要对应于(m₂+1)才能成为根节点，而子节点需要对应于m₂才能成为根节点。但是|b|=0对应于|a|=n–4和ℓ=n–3，这正是我们描述的多边形中相邻顶点为父节点和子节点的条件。

   ○ 如果我们修复这对中的子节点2-cycle，那么也将修复父节点。因此，这种形式的每个子节点都有一个唯一的父节点，其m值大1（通常在(n–1)处返回到1），我们需要证明，在m值重复之前，重复使用唯一的父节点将使我们返回到一个多边形顶点，我们有机会在2-cycle图中形成一个循环。假设我们从一个不是多边形顶点的子节点开始，这样m₂bn(m₂–2)a就不是在循环上等价于序列(n–1)…321了，其中用n替换(m₂–1)。我们将删除下标，只需将从子节点到父节点的映射编写为：

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

  换句话说：如果我们在"|"的左边有(m–1)，并且我们写了从n开始的右边部分，我们从右边部分提取m并将其放在左边，然后在右边的n后面放(m–1)。如果我们继续此过程，并使用一系列修改过的字符串a'etc.来保持统一的模式，我们有：

  (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)步之后，我们最终精确地得到根节点的下降序列。

• m₁≠m₂–1。那么m₁必须是q₂的数字之一，并且为了不简单地在索引交换的情况下重复前面的情况，我们还必须要求m₂≠m₁–1。因此，在我们在(n –1)处换行的通常循环排列中，m₁和m₂必须相差1以上。所以我们的两个2-cycles将是以下形式：

  m₁|n(m₁–1)a₁m2b₁
  m₂|n(m₂–1)a₂m1b₂

  或者，如果我们将它们旋转成合适的形状以检查交叉点：

  m₁|m₂b₁n(m₁–1)a₁
  m₂|m₁b₂n(m₂–1)a₂

  但这两个循环永远不会相交，因为在这两种情况下，n右边的不同数字意味着b₁n(m₁–1)a₁和b₂n(m₂–1)a₂永远不会是相同的模的旋转。（引用结束）

        最后任选多边形上两个相邻的顶点（两个2-cycles），找到两个2-cycles的公共1-cycle。融合前，在“公共但不完全公共（排列顺序不一样）”的两个1-cycles中任选一个，把选的这一个1-cycle的开始排列叫做u，结束排列叫做v，v沿着⇒到达的排列叫做s，最后按照之前图片中的方法，完成超排列。

*如果你想证明拥有公共1-cycle的任意两个2-cycles可以融合，可以把公共1-cycle分成四截字符串，做到四个端点接着四截不同的字符串就行了。

(   E   N   D   )