在4Chan討論如何播放《涼宮春日》動畫，匿名網民為組合數學難題帶來進展

改編自日本作家谷川流輕小說作品的動畫《涼宮春日的憂鬱》2006年版總共有14集，首次播出時電視台播放順序並未循從故事發展時序。到了2009年，動畫再次播放，但按故事發生時序播出，並在中途加入新作品。由於2006年版本的播放順序跟故事發生的時序有別，網絡上有不少關於應以甚麼順序看這套動畫的討論。

2011年，有人在貼圖討論版網站4Chan的科學及數學版（/sci/）上提出「涼宮春日問題」︰如果要把《涼宮春日的憂鬱》（2006年版，下同）所有可能的播放次序都看一遍，最少要看多集？

排序問題

一般來說，如果動畫有n集的話，可能的排序就會有 1 × 2 × 3 ×… × n 個，這數字稱為n的階乘（factorial），記作「n!」。隨着n越來越大，n!會急劇增長，14集的動畫總共有14!個可能次序，即有87,178,291,200——即近872億——種可能。

14集實在太多，讓我們先從簡單的例子開始。假設動畫只有兩集，播放排序僅得兩個可能，我們可以先順次序看，然後再倒轉看——以數字代表集數的話如下︰1, 2, 2, 1。如果我們只在意排序，就不必重複看第二集兩次，以「1, 2, 1」的方式看三集便能達成目標。

假設動畫有三集，則有6個可能的播放次序︰

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

如果以「1, 2, 3, 1, 2, 1, 3, 2, 1」的次序觀看，便可以把上述6個可能排序都看了一遍。

數學上每一個可能的次序稱為「排列」（permutation），直觀地理解，就是把n件東西不重複又沒有遺漏地排隊（為方便起見，我們可以把這n件東西以數字代表）。

至於上述的「涼宮春日問題」則討論另一個相關概念，稱為「超排列」（superpermutation）。對於任何數字n，「n-超排列」就是一個數列，當中包含了n件東西的所有排列。這樣說好像很抽象，不過我們其實已在上文見過︰「1, 2, 1」就是一個「2-超排列」；「1, 2, 3, 1, 2, 1, 3, 2, 1」就是一個「3-超排列」。

最小超排列問題

換言之，只要跟着一個「14-超排列」去播放《涼宮春日的憂鬱》，你就能夠以所有可能的次序去看完這套動畫——前提是你有足夠時間。而「涼宮春日問題」的重點在於以「最少的集數」去看完，用數學家的語言來說，就是要找到一個「最小超排列」（minimal superpermutation）。

早在1993年，已有數學家提出尋找最小超排列的問題。對於較小的數字，數學家已經找到其最小超排列。假如總共有5集動畫，按以下次序播放153集便能夠看完所有可能排序︰

1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1, 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4, 2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2, 4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 1, 2, 1, 3, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4, 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 2, 4, 5, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 1, 3, 2, 1, 4, 5, 3, 2, 1, 4, 3, 5, 2, 1, 4, 3, 2, 5, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1

要到2014年，才有人證明不存在長度小於153的「5-超排列」。過往有數學家猜想，最小的「n-超排列」長度為 1! + 2! + 3! + ... + n!。當n等於5或以下時，這個猜想成立，不過數學家候斯頓（Robin Houston）在2014年找到了一個長度為872的「6-超排列」，比起猜想的長度873短。即使如此，他也不確定自己找到的是最小超排列。

在上個星期五，科幻小說家伊根（Greg Egan）在Twitter表示他根據數學家威廉斯（Aaron Williams）一篇論文預印本，修改其方法後找到一個產生超排列的演算法。伊根指他的演算法所產生的最小「n-超排列」長度為 n! + (n-1)! + (n-2)! + (n-3)! + (n-3)，當n大於6的時候，長度就會小於猜想的數字，他更寫了一個程式，得出7-／8-／9-超排列。

利用伊根的公式計算——假設他的方法正確——如果要看完14集涼宮春日動畫的各種順序，「只需要」看93,924,230,411集就行。伊根的演算法為最小超排列找到長度上限，那麼下限是多少呢？

來自4Chan的證明

上星期二侯斯頓發現，在一個討論「涼宮春日問題」的網站上，有條公式計算最小超排列的長度下限，而這條公式是已知的最佳結果。網站的內容正好來自2011年4Chan上的討論。