42404 從數學競賽到數學研究 ─ 從2002-C6說起
從數學競賽到數學研究 ─ 從2002-C6說起

此文為筆者於 2018 年寒假對新加坡萊佛士書院與建國中學科學班與資優班的同學預定演講內容的前半。 兩國的優秀同學互相訪問行之有年, 志在即將到來的亞太數學競賽 (APMO) 與國際數學競賽 (IMO)。 這些同學互相激勵, 非常值得鼓勵。 本文以一個數學競賽的題目為引子, 希望能引領這些優秀的同學一窺更深刻, 也更令人興奮的數學研究天地。

1. 尋找排列

我們從一個問題開始。 2002 年 IMO 的一題組合預選題是這樣的。

問題1: 設 $n$ 是正偶數, 證明存在一個 $1,2,\ldots , n$ 的排列 $x_1, x_2,\ldots , x_{n}$ 使得對於任何 $1\le i\le n$, 都有 $x_{i+1}$ 是 $$2x_i, 2x_i-1, 2x_i-n, \mbox{ 或 } 2x_i-n-1$$ 四者之一。 其中 $x_{n+1}=x_n$.

白話來說就是, $n$ 是偶數時你一定可以把 $1,2,\ldots , n$ 排成一圈, 讓下一個數是當前這個數的兩倍再減去 $0,1,n$ 或 $n+1$。

習題1: 動手做實驗, 做 $n=2,4,6,8,10,12$ 的情況。

嘗試錯誤可以在 $n=2,4,6,8$ 得到以下的解 (也許有不同的解)。

$$1,2$$ $$1,2,4,3$$ $$1,2,3,6,5,4$$ $$1,2,4,8,7,6,3,5$$ 但之後就愈來愈複雜, $n=10, 12$ 後用嘗試錯誤也不容易找了, 而且目前找到的排列看起來也沒什麼規律。 的確, 這個問題不容易。 IMO 的預選題題號按照難度遞增, 當年組合預選題共有七題, 它是第六題, 底下簡稱為 2002-C6。

怎麼辦呢? 嘗試的過程中不難發現以下切入點。 比如 $n=6$, 則 $1$ 的後面可以接 $2,1$; 而 $2$ 的後面可以接 $4,3$; 以此類推, 到 $6$ 的後面可以接 $6,5$。 如果由 $a$ 可以接到 $b$, 就從 $a$ 往 $b$ 畫一條有向邊 $$a\longrightarrow b,$$ 將所有可以接的情況畫出來, 就得到一個有向圖 (directed graph) $G$。 $n=6$ 所得的圖如下。

如果能找一個迴路經過每一頂點再回到出發點, 問題就解決了。 把此圖整理如下, 馬上可以看出 $1,2,3,6,5,4$ 是一個解, 而且也只有這個解。

習題2: 畫出 $n=8,10,12$ 的有向圖, 並求原問題的解。

所以理論上畫出有向圖 $G$, 然後找個迴路經過每個點就成了。 用圖論 (graph theory) 的語言來說, 就是要找 Hamiltonian circuit。 但是觀察 $n=2, 4,6,8,10, 12$ 的有向圖, 看不出什麼端倪。 更不幸的是, 組合學上一般來說, Hamiltonian circuit 的存在性是超級未解大難題。

2. 從 Hamilton 到 Euler

所以要想辦法找突破口。 這正是數學競賽的精神, 希望解題者有原創的巧思。 仔細觀察 $n=2$, $4$, $6$, $8$, $10$, $12$ 的有向圖, 還是可以看到蛛絲馬跡 - 這些圖的每個頂點都是兩進兩出。 這個競賽題的巧妙和難點是要 構造一個新的圖 , 將問題從找 Hamiltonian circuit 換成找 Eulerian cycle。 所謂的 Eulerian cycle 就是一筆畫問題, 要找一個迴圈把每條邊走完 (頂點可以重複用) 再回到出發點。 Eulerian cycle 比起 Hamiltonian circuit 容易處理多了。

按照以下方式構造有向圖, 並在邊上給編號:

先取 $m=\frac{n}{2}$ 個點, 點的編號為 $1,2,\ldots ,m$。 由點 $i$ 指出兩條邊, 此兩邊的標號分別為 $2i-1, 2i$. 另外也有兩條邊指向點 $i$, 這兩邊的標號為 $i, i+m$。 邊的編號皆以模 $n$ 計。

敘述看似複雜, 但用例子來看就很簡單。 以 $n=6$ 和 $n=8$ 為例, 構造如下, 一般情形依此類推即可。

因此得到 $n=6$ 和 $n=8$ 的有向圖如下。

注意 $n=6$ 時唯一的一筆畫走法中, 把邊的編號記錄下來得到 $1,2,3,6,5,4$, 正是競賽題的解。 $n=8$ 的其中一個一筆畫走法中, 記錄邊的編號得 $1,2,4,8,7,6,3,5$, 另一個走法是 $1,2,3,6,4,8,7,5$ 也都是競賽題的解。

習題3: 仿上述作法, 畫出 $n=4,10,12$ 的有向圖, 並寫出原競賽問題的至少一個解。

所以, 我們如果能說明 (i) 這樣構造出來的圖一定可以一筆畫 (ii) 把邊記錄下來就是我們要的排列, 那問題就解決了。

先處理 (i). 無向圖的一筆畫問題是大家熟悉的: 連通無向圖有 Eulerian cycle 的充要條件是每個點的 degree $d(v)$ (和此點相接的邊數) 是偶數, 有向圖有類似的結果。 令指向頂點 $v$ 的箭頭數為 $d^-(v)$, 稱為 $v$ 的 in-degree; 從 $v$ 射出的箭頭數為 $d^+(v)$, 稱為 $v$ 的 out-degree。

定理1:[有向圖有Eulerian cycles 的充要條件] 連通有向圖 $G$ 有 Eulerian cycle 的充要條件是對於任意頂點 $v$ 都有 $$d^+(v)=d^-(v).$$

習題4: 證明此定理。

回到競賽問題, 易看出構造出的圖 $G$ 是連通的, 且每個頂點都有兩個往內箭頭, 兩個往外箭頭 (2-in, 2-out), 因此必有 Eulerian cycle。

剩下來要說明 (ii): 沿著 $G$ 的任一個 Eulerian cycle 走, 記錄各邊的標號, 就是我們要的排列。 但這由 $G$ 的構造方法不難解決, 當作習題。

習題5: 設上述構造的 $G$ 有 $n$ 條邊 (故有 $\frac{n}{2}$ 個頂點), 證明沿著 $G$ 的一個 Eulerian cycle 走並記下各邊編號, 則下一邊的編號必為當前此邊編號的兩倍再減去 $0,1,n,n+1$ 四者之一。

因此, 原競賽問題所求的排列一定存在。 $\Box$

至此, 競賽問題 2002-C6 已經解決了。 但是旅程才要開始。

3. 有幾個排列?

組合學的研究中, 解決了「存在性」(有沒有) 之後, 下個自然的問題就是「計數」(有幾個)。 我們問:

問題2: 設 $n$ 是正偶數。 有多少 $1,2,\ldots , n$ 的排列 $x_1, x_2,\ldots , x_{n}$ 使得對於任何 $1\le i\le n$, 都有 $x_{i+1}$ 是 $2x_i, 2x_i-1, 2x_i-n, 2x_i-n-1$ 四者之一。 其中 $x_{n+1}=x_1$?

感覺這應該會比原競賽問題難。 解答留到最後再說, 讀者不妨先探索一番。

習題6: 試找出 $n=10$ 時的 $3$ 個排列 (規定由 $1$ 開始)。 試問 $n=12$ 時有幾個排列?

4. BEST 定理

數學家喜歡問一般的問題 : 如果有向圖 $G$ 可一筆畫, 那有多少個 Eulerian cycles? 比如圖一, 固定 $1\to 2$ 為起始邊, 容易得出有 $3$ 個 Eulerian cycles。

圖1:一個有向圖與它的三個 Eulerian cycles

但即使是簡單的圖, 慢慢數也不容易。

圖2:此圖有幾個 Eulerian cycles?

習題7: 圖二有多少個 Eulerian cycles?

圖二有 32 個 Eulerian cycles, 你數對了嗎 ? 這麼簡單的圖都很難數, 更不要說複雜的圖了。 但令人驚訝的是, 對於一般的有向圖, 的確有一個公式可以算出 Eulerian cycle 數。 這個結果結合了來自四個數學家 de Bruijn, Aardenne-Ehrenfest, Smith, Tutte 的兩篇論文而得, , 取四個姓氏的第一個字母, 稱為 BEST 定理。

首先需要一些名詞, 有向圖 $G$ 的頂點集合為 $V$, 令 $v\in V$ 為某個頂點, $T$ 為一個子圖。 若其他任意頂點 $u\ne v$ 都有唯一的方法沿 $T$ 的邊走到 $v$, 那我們就稱 $T$ 為一棵以 $v$ 為根的生成樹 (spanning tree rooted at $v$)。 例如, 圖一以 $1$ 為根的生成樹共有三個, 如下。

在數 Eulerian cycles 時, 為了不要重複算, 我們固定都從 $G$ 中某個選定的頂點 $v_0$ 出發 ($v_0$ 可以是 $v_1,\ldots v_n$ 中的任意一個, 只要選定就好), 並且也固定選取從 $v_0$ 出發的某一邊為第一邊。 這樣約定後, 令 $\epsilon(G)$ 為 Eulerian cycles 數, $\tau(G)$ 為以 $v_0$ 為根的生成樹個數。 BEST 定理把兩者神奇地聯繫起來。

定理2:[BEST 定理] 若有向圖 $G$ 有 Eulerian cycle, 則 Eulerian cycle 的數量 $\epsilon(G)$ 可按下式計算。 $$\epsilon(G)= \tau(G) \cdot \prod_{v\in V} (d^+(v)-1)!.$$

例如, 圖二的有向圖共有八個以 $3$ 為根的生成樹, 如下。

因此由 BEST 定理, 圖二有 $$8\times 2\times 1\times 2\times 1=32$$ 個 Eulerian cycles。

習題8: 競賽問題中, $n=10$ 的圖有多少個 Eulerian cycles?

要怎麼證明 BEST 定理呢? 觀察定理的形式, 如果我們能證明每個以 $v_0$ 為根的生成樹都可以製造出 $\prod_{v} (d^+(v)-1)!$ 個 Eulerian cycles, 證明就完成了。 關鍵是以下兩個大步驟, 當作兩個習題。

習題9: 對於一個以 $v_0$ 出發的 Eulerian cycle, 若對於每個 $v\ne v_0$ 頂點, 把最後一次離開 $v$ 的邊塗上紅色。 則會得到一個以 $v_0$ 為根的生成樹。

習題10: 給定一以 $v_0$ 為根的生成樹 $T$。 由 $v_0$ 出發沿著圖 $G$ 的邊亂走, 非不得已才用 $T$ 的邊。 則不會出現卡住不能走的情況, 而且可以走完所有的邊又回到 $v_0$, 亦即可得到 Eulerian cycle。

因此, 固定一個以 $v_0$ 為根的生成樹 $T$, 對於 $v_0$, 離開它的第一邊是固定的, 故之後再離開它共有 $(d^+(v_0)-1)!$ 種選法。 對於每一個 $v\ne v_0$, 除了最後一次離開它是走 $T$ 中的邊之外, 之前都可以亂選邊, 所以有 $d^+(v)-1$ 種選法。 因此對於這棵樹 $T$, 可以製造出 $$\prod_{v\in V} (d^+(v)-1)!$$ 個 Eulerian cycles。 又 $T$ 的選法有 $t(G)$ 種。 因此 BEST 定理得證。 $\Box$

仔細想一下, BEST 定理的左邊是 Eulerian cycles 數 (雖然固定是從 $v_0$ 出發的某一邊起算, 但算出來後的量和 $v_0$ 選哪一點是無關的), 而右邊的 $\prod_{v\in V} (d^+(v)-1)!$ 也和 $v_0$ 的選取無關。 因此我們得到一個意外的結果。

習題11: 如果 $G$ 有 Eulerian cycle, 則以 $v_0$ 為根的生成樹, 其數量與 $v_0$ 選哪一個點無關。

習題12: 你能否直接證明這個結果?

5. 生成樹的個數

所以, BEST 定理把計算 Eulerian cycles 的數目化為計算以 $v_0$ 為根的生成樹的數目。 但是問題還是沒有解決啊, 那到底有幾個生成樹呢?

接下來線性代數就登場了。 設有向圖 $G$ 的頂點是 $v_1,v_2,\ldots ,v_n$。 令 $m_{i,j}$ 是由 $v_i$ 指向 $v_j$ 的邊數, 而 $d_i:=d^+(v_i)$ 是 $v_i$ 的 outdegree。 我們定義兩個 $n\times n$ 的矩陣: $$D:=\mbox{diag}(d_{i})_{1\le i\le n},\qquad A:=(m_{i,j})_{1\le i,j\le n}$$ 也就是說, 對角線矩陣 $D$ 記錄各頂點的 degrees, $A$ 記錄頂點之間的連邊情形。 由此, 再定義 $G$ 的 Laplace 方陣 $L$ 為 $$L:=D-A.$$

例如圖三的有向圖

圖3:圖三

可求出 $$D= \left[ \begin{array}{ccc} ~3~ & ~0~ & ~0~ \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{array} \right] , \qquad A= \left[ \begin{array}{ccc} 1 & 1 & 1 \\ ~1~ & ~0~ & 1 \\ 1 & 1 & ~0~ \\ \end{array} \right], $$ 因此 $$L= D-A= \left[ \begin{array}{ccc} 2 & -1 & -1 \\ -1 & 2 & -1\\ -1 & -1 & 2 \\ \end{array} \right].$$ 於是就可以算生成樹的個數了 --- 用如下的有向圖矩陣樹定理 (Matrix tree theorem)。

定理3:[有向圖的矩陣樹定理] 任取一組 $1\le s,t\le n$。 令 $L_{s,t}$ 為將 Laplace 方陣 $L$ 去掉第 s 列第 t 行所得的 $(n-1)\times (n-1)$ 方陣。 任取 $v_0$, 則以 $v_0$ 為根的生成樹個數是 $$(-1)^{s+t} \det L_{s,t}.$$

我們先學會怎麼用。

習題13: 利用矩陣數定理, 檢驗圖二的確有 $8$ 個生成樹, 從而有 $32$ 個 Eulerian cycles。

習題14: 原來 2002-C6 競賽題中, 有多少個滿足條件的長度 $8$ 的排列? 有多少長度 $10$ 的排列?

矩陣樹定理的證明需要一點線性代數的知識, 但是本質上是用數學歸納法。

習題15: 試對邊數做歸納, 用數學歸納法證明此定理。

有線性代數基礎的同學亦可以試著用 Cauchy-Binet 公式直接證明。 附帶一提, 矩陣樹定理亦有無向圖的版本, 用來計算無向圖的生成樹 (spanning trees) 個數。 且不難從有向圖的版本得到, 我們當作習題。

習題16: 導出無向圖的矩陣樹定理 (要特別留心由 $v$ 連回 $v$ 的迴圈邊要怎麼處理)。

習題17: [Cayley 定理] 證明完全圖 $K_n$ 有 $n^{n-2}$ 個生成樹。 也試試看完全不要用矩陣證明這個重要結果。

至此, 理論上我們完全解決了有向圖 $G$ 的 Eulerian cycles 的計數問題。 對於一個有向圖, 用矩陣樹定理可以先算出生成樹的個數, 再用 BEST 定理就可得到 Eulerian cycles 數。 當然, 我們總是想知道有沒有一個公式? 不然 $n=1000$ 時用矩陣樹定理就要去算一個 $999\times 999$ 的行列式, 這也太不實際, 我們繼續看下去。

6. 競賽題的由來

這 2002-C6 題目到底是怎麼出現的? 動機和背景是什麼? 為什麼有人會去把數字排成一圈, 而且規定下一個是當前這一個的兩倍減 $0,1,n,n+1$ 呢? 總有個道理吧, 否則這個問題一點意義也沒有啊。

這個背景稱為 de Bruijn 問題, 我們先看看這個益智遊戲:

能否將八個 $0$ 或 $1$ 排成一圈, 使得讀三個相鄰位元 (當作二進位來讀) 剛好出現 $000,001,\ldots , 111$ 各一次?

答案是可以的, 比如 $00011101$ 就是一個解, 如下圖。

由此可以讀出 $$000, 001,011,111,110,101, 010, 100.$$

習題18: 將一共 $16$ 個 $0$ 或 $1$ 排成一圈, 使得讀四個相鄰位元 (當作二進位來讀) 剛好出現 $0000,0001,\ldots , 1111$ 各一次。

注意到數碼 ($0$ 或 $1$) 的個數是有限制的: 讀三個位元 ($000,\ldots , 111$) 共有八種可能結果, 所以需要八個數碼才能讓每個數碼當開頭讀出來不一樣。 讀四個位元共有 $16$ 種可能, 所以需要 $16$ 個數碼。 同理, 類似的問題只有在排成一圈的數碼有 $2^r$ 個時才有意義。 此即 de Bruijn 問題:

是否能將 $2^r$ 個 $0$ 或 $1$ 排成一圈, 使得連續讀 $r$ 個相鄰位元時, 剛好每個不同的字串恰出現一次?

答案是可以, 即 de Bruijn 問題一定有解。

定理4:[de Bruijn 問題必有解] 可以把 $2^r$ 個 $0$ 或 $1$ 圍成一圈, 使得連續讀 $r$ 個相鄰位元 (當作二進位) 時, 從 $000\dots 0$ 到 $111 \dots 1$ 的 $2^r$ 種字串都恰好出現一次。

證明我們留待下一節。 底下先來觀察一下到底發生什麼事, 以 $00011101$ 所得的 $000$, $001$, $011$, $111$, $110$, $101$, $010$, $100$ 八個字串可以清楚說明概念。 因為每次讀三個位元, 慢慢順時針移動. 因此從目前的字串往下一個字串, 一定是 $$在最右邊補上一個數碼, 然後去掉最左邊的數碼。$$

但是這在十進位中是什麼意思呢? 在二進位中, 最右邊補 $0$ 就是乘兩倍, 最右邊補 $1$ 就是乘兩倍再加 $1$, 而「去掉左邊的數碼」 就是相當於十進位中減 $0$ 或減 $8$ (如果此數碼為$1$)。 換句話說, 在十進位中由 $a$ 移動到下一個數 $b$ 一共有四種可能: $$b=2a, \quad 2a+1, \quad 2a-8,\quad 2a-7.$$ 檢驗一下, 這八個字串寫回十進位是 $$0,1,3,7,6,5,2,4$$ 的確就是這樣的規則。

如果我們把這字串取補數 ($x$ 變成 $8-x$), 字串變成 $$8,7,5,1,2,3,6,4,$$ 則由 $a':=8-a$ 移動到下一個數 $b':=8-b$ 的關係可以計算而得:

$b=2a$ $\Leftrightarrow$ $(8-b)=2\cdot (8-a)-8$ $\Leftrightarrow$ $b'=2a'-8$
$b=2a+1$ $\Leftrightarrow$ $(8-b)=2\cdot (8-a)-9$ $\Leftrightarrow$ $b'=2a'-9$
$b=2a-8$ $\Leftrightarrow$ $(8-b)=2\cdot (8-a)$ $\Leftrightarrow$ $b'=2a'$
$b=2a-7$ $\Leftrightarrow$ $(8-b)=2\cdot (8-a)-1$ $\Leftrightarrow$ $b'=2a'-1$

看, 這就是原來競賽問題 $n=8$ 的形式: 下一項是這一項的兩倍再減 $0,1,8,9$。

之前解釋過 de Bruijn 問題只對 $n=2^r$ 有意義. 但是變換成這個形式: 「下一項是這一項的兩倍再減 $0,1,n,n+1$」, 則 $n$ 就可以擺脫 $2^r$ 的限制了。 所以, 我們終於知道競賽問題的由來了:

競賽問題 2002-C6 是 de Bruijn 問題的推廣, 目的是把$n=2^r$ 推廣到所有偶數 $n$。

這是一個令人舒服的結果 (至少我個人很舒服), 這個問題變得「有意義」, 而且開始有數學上的深度了。

7. de Bruijn 圖

我們先證明前一節留下來的問題: 長度為 $n=2^r$ 的 de Brujin 字串必定存在。 方法和 2002-C2 非常像: 構造圖, 然後找 Eulerian cycle。 一幅畫勝過千言萬語。圖四是 $n=4,8$ 的 de Bruijn 問題對應的圖 ($n$ 為有向邊的邊數), 一個 Eulerian cycle 就相當於一個解。同學可檢驗 $000$, $001$, $011$, $111$, $110$, $101$, $010$, $100$ 是右圖的一個 Eulerian cycle。

圖4:$n=4,8$ 的 de Bruijn 問題對應的圖

這些圖稱為 de Bruijn 圖, 是一個重要的圖類, 在資訊科學與通訊理論上有相當大的應用。 事實上, 由 $n=2^r$ 的圖可以生成 $n=2^{r+1}$ 的圖, 而且後者恰為前者的線圖 (line graph). 由 $G$ 具體構造線圖 $L(G)$ 的方法如下:

  1. $G$ 的一條邊 $e_i$ 當作 $L(G)$ 的一個頂點 $v_i$。
  2. 對於 $G$ 中一組連續的兩條邊 $e_i, e_j$ (即走了 $e_i$ 後, 可以再馬上接著走 $e_j$) , 則在 $L(G)$ 中就畫有向邊 $v_i\to v_j$。

習題19: 畫 $n=16$ 的 de Bruijn 圖。

現在, 證明長度為 $n=2^r$ 的 de Brujin 字串存在性變得非常容易:

習題20: 證明 de Bruijn 圖若頂點有 $2^r$ 個, 邊就有 $2^{r+1}$ 條, 且是 2-in 2-out。 並說明 Eulerian cycle 對應到一個 de Bruijn 問題的解。

讀者應該可以馬上聯想, 既然一個一筆畫的方法就是一個解, 我們就可以用 BEST 定理來計算有多少個解。 沒錯。 為方便起見把 de Bruijn 的解寫成字串的樣子 (比如 $00011101$), 叫做 de Bruijn 字串。 此結果用 BEST 定理的確可以做, 但是計算非常繁雜, 比較好的作法會牽涉到圖的特徵值問題, 屬於代數圖論的範圍, 可參考。 總之結果是這樣:

定理5: 長為 $2^r (r\ge 1)$ 的 de Bruijn 字串, 若固定開頭為 $0000\dots$ ($r$ 個 $0$), 一共有 $$2^{2^{r-1}-r}=1, 1, 2, 16, 2048, 67108864, 144115188075855872,\ldots $$ 個。

這個數量多到超乎想像: 有 $67108864$ 個方法將 $64$ 個 $0$ 或 $1$ 圍成一圈, 使得 $000000$, $000001$, $\dots$, $111111$ 這 $64$ 個字串中的每一個都在圓周上出現恰好一次!

如果不要限制要全 $0$ 字串開頭, 則 de Bruijn 字串個數還要乘以 $2^r$ 倍, 因此一共有 $$2^{2^{r-1}}$$ 個。 注意到 $$2^{2^{r-1}}\times 2^{2^{r-1}} = 2^{2^r}. $$ 等號左邊是 '一組' 長為 $2^r$ 的 de Bruijn 字串的組數。 等號右邊是長為 $2^r$ 的 $0,1$ 字串的個數。 據此, 組合學大師 Stanley 問了一個問題:

習題21: 令 \begin{eqnarray*} A&=&\{(w_1,w_2): w_1,w_2 \mbox{ 為長為 $n=2^r$ 的 de Bruijn 字串 }\}\\ B&=&\{u: u \mbox{ 為長為 $n=2^r$ 的 $01$ 字串 }\} \end{eqnarray*} 試找一個這兩個集合間的一個一一對應。

比如說, 當 $r=2$, 即長為 $n=4$ 時, 你要找到底下兩個集合之間的對應: \begin{equation*} \begin{split} A:=\{(0011, 0011), (0110, 0011), (1100, 0011), (1001, 0011),\\ (0011, 0110), (0110, 0110), (1100, 0110), (1001, 0110),\\ (0011, 1100), (0110, 1100), (1100, 1100), (1001, 1100),\\ (0011, 1001), (0110, 1001), (1100, 1001), (1001, 1001)\} \end{split} \end{equation*} 與 \begin{equation*} \begin{split} B:=\{0000, 0001,0010,0011,0100, 0101, 0110, 0111,\\ 1000, 1001,1010,1011,1100, 1101, 1110, 1111\} \end{split} \end{equation*}

8. de Bruijn 推廣圖

競賽問題 2002-C6 既源於 de Bruijn 問題, 因此此競賽問題得到的圖, 都可視為 de Bruijn 推廣圖 (generalized de Bruijn graphs)。 一個自然可預期的結果就是:

習題22: 證明 $2n$ 個頂點的 de Bruijn 推廣圖就是 $n$ 個頂點推廣圖的線圖。

要用 BEST 定理的關鍵是需要生成樹的個數。 因此現在要看線圖 $L(G)$ 與原圖 $G$ 的生成樹之間有什麼關係。 資訊大師 Knuth 利用矩陣樹定理證出這個結果

定理6:[線圖的生成樹] 令 $V$ 為有向圖的頂點集, 若 $G$ 的每個頂點都有 $d^{-}(v)\ge 1$, 則 $$\tau(L(G))=\tau(G)\prod_{v\in V} d^+(v)^{d^{-}(v)-1}.$$

習題23: 利用 Knuth 的定理求 de Bruijn 問題解的個數。

回到我們原來的問題 2: 滿足 2002-C6 敘述的 $1,\ldots ,n$ 的排列有幾個? 有沒有像 $n=2^r$ 個頂點時 $2^{2^{r-1}-r}$ 那麼漂亮的公式? 根據習題 22 的線圖結果, 可得有底下這個表。 每一橫列都是一連串的線圖的頂點數, 第一列就是原始的 de Bruijn 問題。 線圖的生成樹可以用 Knuth 的定理求得, 所以第一行的圖才是關鍵: 如果第一行的圖可以得到答案, 基本上就做完了。

2 $\to$ 4 $\to$ 8 $\to$ 16 $\to$ $\dots$
6 $\to$ 12 $\to$ 24 $\to$ 48 $\to$ $\dots$
10 $\to$ 20 $\to$ 40 $\to$ 80 $\to$ $\dots$
14 $\to$ 28 $\to$ 56 $\to$ 112 $\to$ $\dots$
$\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $\vdots$

但非常不幸, 第一行的圖有幾個生成樹, 還是很難算。 事實上這個問題 真的不容易, 一直到兩年前才解決。 解決的切入方法利用到高等的抽象代數, 繞了一大圈。 要大致說清楚, 還要再寫幾篇文章, 所以這裡只給非常粗略的介紹: 從一個有向圖可以得到一個在統計物理與代數組合上都重要的群, 稱為這個圖的沙堆群 (sanpile group), 它是一堆循環群的直和。 一個已知的重要定理說,

沙堆群的元素個數就是生成樹的個數。

因此只要能求出沙堆群, 事情就了了。 但是即使是非常簡單的圖, 沙堆群通常比單純算生成樹更困難。 你要問, 那這樣不是自討苦吃嗎? 非也, 從抽象代數切入的好處是代數的理論豐富, 攻擊問題的武器就多了。 總之, 經過數學家的努力, de Bruijn 圖的沙堆群到 2011 年終於找出來, 而 de Bruijn 推廣圖的沙堆群 2015 才得到

現在既然有沙堆群, 就可以算生成樹個數, 再用 BEST 定理就可以得到 Eulerian cycles 個數, 也就是問題 2 的排列數。 總之, 問題 2 的確是有一個「公式」解. 因為符號繁雜, 敘述在此略去。 底下只列出由這個公式解算出來的 $n=2m$, $1\le m\le 18$, 的結果。

定理7: 設 $n=2m$. 要求將 $1,2,\ldots , n$ 的排列 $x_1, x_2,\ldots , x_{n}$ 使得對於任何 $1\le i\le n$, 都有 $x_{i+1}$ 是 $2x_i, 2x_i-1, 2x_i-n, 2x_i-n-1$ 四者之一, 其中 $x_{n+1}=x_n$。 則共有 $$\langle 1, 1, 1, 2, 3, 4, 7, 16, 21, 48, 93, 128, 315, 448, 675, 2048, 3825, 5376,\ldots \rangle _{m=1}$$ 種方法。

那個第三項的 '$1$' 就是 $n=6$ 時的 $1,2,3,6,5,4$ 這個唯一解. 而第四項的 '$2$' 就是 $n=8$ 時的 $1,2,4,8,7,6,3,5$ 與 $1,2,3,6,4,8,7,5$ 這兩個解。 所以習題 3 在 $n=10$ 時有 $3$ 個排列, 而 $n=12$ 時有 $4$ 個排列。

真沒想到從一個單純的數學競賽問題, 我們可以一路從兩百年前的 Euler 談到這一兩年的學界新結果, 認識了幾個優秀數學家的工作, 每一篇論文都推進了數學的進展。 數學學海真是無涯。

最後我們留下一個問題, 對於資訊科學有興趣的同學會覺得非常有挑戰性: 「存在性」與「計數」都解決了, 另一個面向就是「設計」。

習題24: 找一個有效率的方法生成這些排列. 換句話說, 找一個有效率的方法生成 de Bruijn 推廣圖的 Eulerian cycles。

9. 註記

de Bruijn 圖或其推廣圖引出的數學意外地豐富, 在工程及資訊等其他領域上有許多應用, 相關研究仍然非常活躍。 習題 21 的對應頗不容易, 解決不過是近十年的事, 也許同學可以找到更簡單的方法。 沙堆群是最近的結果, 定理 7 所得到的數列頗為神秘, 仍然有許多問題待釐清。

無向圖的 Eulerian cycles 的個數居然沒有公式, 目前學界知道這是一個 #P-完全問題 (#-P complete)。 有可能有「無向圖的 BEST 定理」嗎?

關於 Eulerian cycles 的研究近十年來發展出 interlace polynomial 的理論, 是令人興奮的進展。 不僅可以求 2-in 2-out 圖 Eulerian cycles 的個數, 更能算出「Eulerian 分解」的個數。 那你要問, de Bruijn 圖或推廣圖的 interlace polynomial 呢? 據筆者所知, 仍然是未解問題。

當日預定演講內容的後半是沙堆群, interlace polynomial, 與 de Bruijn 圖相關的後續研究。 但事實證明我太貪心, 演講當日同學參與踴躍, 導致時間緊迫, 連前半都無法講完。 因此藉此文把前半整理一下並稍微提一下後半, 亡羊補牢一番。 在此謝謝建國中學的邀請, 並謝謝徐祥峻博士協助諸多圖形的繪製。

最後回到數學競賽。筆者多次擔任 IMO 台灣國家代表隊的領隊, 對於數學競賽有一些感想。 一些頂尖數學家不太認同數學競賽, 但是弔詭的是又有許多頂尖的數學家年輕時是數學競賽的好手。 這兩者看似矛盾的不協調, 其實是觀點與成長的問題。過度的訓練, 無意義的重複, 鑽牛角尖與技巧, 導致停留在小題目, 期待快速解題或期待巧解的層次, 當然是不好的, 這也是競賽被詬病的主因。 然而健康地看, 數學競賽的初衷是發掘數學天分, 亦可一嘗數學研究苦苦探索的經驗。 若有適當的引導, 一如本文所欲傳達的, 一個好的問題引出一片天地, 可以使同學一窺數學的堂奧。 從而能激發同學追求更高境界的志向, 渴望與熱情, 並在未來能一起加入研究數學的行列。

參考文獻

T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, 1951. R. Arratia, B. Bollobas, G.B. Sorkin, The interlace polynomial of a graph. Journal of Combinatorial Theory, Series B, 92(2), 199-233, 2004. H. Bidkhori and S. Kishore, Counting the spanning trees of a directed line graph. arXiv:0910.3442, 2009. G. R. Brightwell and P. Winkler, Counting Eulerian circuits is #P-Complete, ALENEX/ ANALCO, 259-262, 2005. S. H. Chan, H. D. Hollmann and D. V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields. Journal of Algebra, 421, 268-295, 2015. D. E. Knuth, Oriented subtrees of an arc digraph. Journal of Combinatorial Theory, 3(4), 309-314, 1967. L. Levine, Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364, 2011. R. P. Stanley, Algebraic Combinatorics. Springer, 2013. W. T. Tutte and C. A. B. Smith, On unicursal paths in a network of degree 4. The American Mathematical Monthly, 48(4), 233-237, 1941.

---本文作者任教國立台灣師範大學數學系---