OEIS A276449 數列的故事 (旋轉碰碰棋)

http://4rdp.blogspot.com/2016/11/oeis-a276449.html

圖片來自 FB

今年暑假貼出一篇訓練數學感 108 ─ 碰碰棋，經過問題討論後又意外找到四組數列，本文就是把這個故事做個紀錄，有興趣的朋友可以接續我們的努力再找其它數列。

碰碰棋，這款桌遊是在 International Mathematical Olympiad 2016 FB 官網看到的，我不知道它的正式名稱，就暫時稱它為碰碰棋，遊戲規則蠻簡單，在 5x5 棋盤有五顆棋子任意散佈，每顆棋子可以橫走或直走，直到該棋子遇到邊界或是其它棋子就停下來，現在就如圖所示，看如何移動棋子讓紅棋停在棋盤正中間。官方的進階玩法還限制不能去碰邊界，如果這樣，請問你會怎樣走？

因為這遊戲棋子可以任意布局，從數學的角度來看，這是一個排列組合的問題，但是它有趣在棋盤方正，可以旋轉，讓我想到一個進階題目，就是計算旋轉的組合排列！

數列尋找的老班底除了赤子西瓜與孫老師外，這回還多了網友 tora 及我的小朋友 Andy，不過研究主力在赤子西瓜與 tora 身上，我負責彙整，flyingdusts 提供意見，而 Andy 計算組合數值，就這樣分工破解了這個旋轉的組合問題。

這問題說難不難但也不是簡單的問題，因為研究初期為了釐清問題本質，大家陷入膠著狀態 (誤，應該是我陷入膠著狀態)。首先，這是組合還是排列的問題？起初提問這五個棋子有多少種排列方法？因為棋盤有四個邊，如果旋轉後，有相同布局位置要扣除，每個棋子視為不同的物件。 tora 提供一個 (25P5)/4 的解答，但是答案沒這麼簡單，因為必須扣除重複排列的狀況，因為加入了旋轉讓問題難度升高，甚至連我也轉得頭暈算錯。所以我們先把問題修正成棋子都長得一模一樣，求解棋盤旋轉組合問題。另外，研發養成所的數學訓練感系列解題的習慣就是求通解，所以我們把它轉化為 n X n 棋盤放置 n 顆棋子有多少種旋轉組合。

在大家解題昏頭轉向的時候，所幸赤子西瓜提供一個公式解 C(n^2,n) = 4a + 2b + c 而再現生機，因為 a + b + c 就是我們要求的答案，它就是 a (轉四個90度方向後位置都不同的) + b (轉四次90度方向後有兩個位置相同的) + c (轉四個90度方向後位置都相同的)。


剛開始大家逐個畫圖計算，錯誤狀況很多 ......，我提出把棋盤分四個象限，針對狀況 c (四旋 90 度後位置都一樣)，就是第一象限怎樣放棋子，其它象限就跟著擺，例如 4x4 棋盤 c 共有 4 種放法。而狀況 b (轉四次90度方向後有兩個位置相同的)，那就是第一、二象限如何放子，第三、四象限也對應著放，其它的狀況就歸屬狀況 a (旋轉後棋子位置都不一樣)。

有了這樣處理原則，很快就解出狀況 c (四旋皆同)，它還區分三種情形：
一、n = 4*i，剛好棋子數量可以平均分配在棋盤四個象限內。例如，O 空格，X 棋子
   X O O X    O X O O     O O X O     O O O O
   O O O O    O O O X     X O O O     O X X O
   O O O O    X O O O     O O O X     O X X O
   X O O X    O O X O     O X O O     O O O O
二、n = 4*i +1，必有一顆棋子在棋盤正中央，其餘平均分配在棋盤四個象限裡。

X O O O X  O X O O O  O O X O O  O O O X O  O O O O O  O O O O O

O O O O O  O O O O X  O O O O O  X O O O O  O X O X O  O O X O O

O O X O O  O O X O O  X O X O X  O O X O O  O O X O O  O X X X O

O O O O O  X O O O O  O O O O O  O O O O X  O X O X O  O O X O O

X O O O X  O O O X O  O O X O O  O X O O O  O O O O O  O O O O O

三、n = 4*i +2 或 4*i +3，無法平均分佈，就沒有四旋皆同的情形。

狀況 c 公式如下：





但是狀況 b (二旋皆同) 就不容易分辨，起初我也經常錯辨型式，還好 tora 提供兩個簡單的方法，可以幫忙辨別。一個是位置編碼，這樣旋轉後也不會錯認位置，有興趣的人可以參考 tora 的手稿。
   1 2 3 4    4 8 5 1
   5 6 7 8    3 7 6 2
   8 7 6 5    2 6 7 3
   4 3 2 1    1 5 8 4

另一個是試算表編號，例如圖中紅色大字 6，這樣計數數量時才不會遺漏，細節請參考 tora 的試算表。 

二旋皆同狀況，經過研究可以區分偶數及奇數棋盤，例如

X O O      O O X     雖然兩者看起來不同但他們是一群的
O X O      O X O     
O O X      X O O
赤子西瓜定義它們為鏡射組合，90度旋轉後，左右兩圖對稱。
------------------------------------------------
O X O X    X O O O   左邊兩個也是一群的
O O O O    O O O X   
O O O O    X O O O
                  　X O X O    O O O X

狀況 b 的公式如下：





最後是狀況 a (四旋皆異)，我們看個例子比較容易了解，但它們是四個同一群組，
   X X X X   O O O X   O O O O   X O O O
   O O O O   O O O X   O O O O   X O O O
   O O O O   O O O X   O O O O   X O O O
   O O O O   O O O X   X X X X   X O O O

狀況 a 的公式如下：





因此，這四個數列分別如下，列名是依據貢獻以及重要性來排序，感謝網友們的大幫忙：
四旋皆同 c(n) = A276449 = 1, 0, 0, 4, 6, 0, 0, 120, 190, 0, 0, 7140, 11480, 0, 0, 635376, ...
登記發現者 ─ 赤子西瓜、tora、Andy、Bridan

二旋皆同 b(n) = A276451 = 0, 1, 2, 12, 30, 408, 1012, 17920, 45600, 1059380, 2730756, ...
登記發現者 ─ tora、赤子西瓜、Bridan、flyingdusts

四旋皆異 a(n) = A276452 = 0, 1, 20, 448, 13266, 486744, 21474640, 1106532352, ...

登記發現者 ─ Bridan、赤子西瓜、tora

a(n)+b(n)+c(n) = A276454 = 1, 2, 22, 464, 13302, 487152, 21475652, 1106550392, ...
登記發現者 ─ 赤子西瓜、Bridan、tora

這四個數列九月初就在 OEIS 登記，A276449 很快認可發表，但是 A276451 卡關好久，剛開始有 OEIS 義工 Michael De Vlieger 初步檢查數值是否正確，然後由德國物理學家 Wolfdieter Lang 負責審核我的申請，可能跟這個旋轉組合有關係，起初他不明白為什麼 A276451 不是 0, 2, 4, 24, ... 而是 0, 1, 2, 12, ...，我解釋這四組數列有 C(n^2,n) = 4a + 2b + c 依存關係後，他才清楚整體關係，然後建議我用物理軌道術語方式來解釋說明，因此 A276449 為 1-orbit under C_4 (轉四次 90 度一圈)，表示旋轉 90 度只有一種樣態，A276451 為 2-orbits under C_4，90 度旋轉兩種樣態，A276452 為 4-orbits under C_4，90 度旋轉四種樣態，從這裡學到一課。Wolfdieter Lang 還建議我研究 Polya counting，也是關於群組著色旋轉的問題。

另外，尋找數列的同時，Andy 意外發現神奇的組合算式，
C(16,2) = 15 + 14 + 13 + ... + 2 + 1 = 16! / 14! / 2! = 120
以及
C(16,3) = 2 x (1x14 + 2x13 + 3x12 + 4x11 + 5x10 + 6x9 + 7x8) = 16! / 13! / 3! = 560
我從這神奇組合算式受到啟發，提出一個 Bridan 猜想 ─ 數學的組合公式，它與高維空間的特定錐形體是有個對應關係，也就是 m 物任取二個組合像是在計算三角形面積，任取三個組合像是在計算三角錐體積，四維錐形體積就是底部 x 高度 / 4，五維錐形體積就是底部 x 高度 / 5，其餘以此類推。

從這次數列登記過程，可以知道研究旋轉的組合問題的人不多，有興趣的人接下來可以幹什麼？個人直覺如果棋盤是正三角形或是正 N 邊形，應該有奇妙數列可以找，反正我們已經開了歷史先河也留下紀錄，那留些機會給後進努力吧。這回一次囊括四項數列，是今年第三次全新數列斬獲，跟寶可夢抓寶有得拚，話說找數列不是一件容易的事，但是留意生活周遭有趣的事物一定可以發現很多。

最後附上網友 tora 參與這次尋找數列的感言，做為本文結尾：

老實說之前站長寄給我請我幫忙看赤子西瓜的公式的時候，

我實在看不太懂，然後我自己也是一直釐不出一個頭緒來解這題，

就這樣過了好幾天一兩個禮拜，一直沒有回站長信也覺得很不好意思。

直到後來看到赤子西瓜推出的C(N^2,N)=4a+2b+c這公式才有點明白想法。

然後昨天下午在那裏用excel標棋盤的時候也是突然靈光一閃，

才想到把格子標上數字，然後再用取數字去放棋子的方法。

一下子好像就迎刃而解了，反而有點不太相信這麼簡單就算出來了。

解出來以後突然有種滿足又失落的心情，哈。

失落的是覺得自己怎麼沒有早點想到這解法。

延伸閱讀
一、想知道什麼是 OEIS ，請看 OEIS A274119 數列的故事 (2003倍數)
二、想知道 OEIS 數列申請程序，請看 OEIS A273916 數列的故事 (Bingo-4)
三、Andy 的神奇算式 以及 組合公式對應高維錐體的 Bridan 猜想