2016年8月13日 星期六

Andy 的神奇算式 以及 組合公式對應高維錐體的 Bridan 猜想

http://4rdp.blogspot.com/2016/08/andy-bridan.html

今天這篇文是想分享一個數學公式的幾何意義猜想,這個靈感來自我的小朋友 Andy 的神奇組合算法。

大家在學習排列組合時,數學老師都會教導公式解,你可曾想過以別種方法計算,替代大家所熟用的公式?這先從排列公式談起,


假設有 16 個東西要排列,那麼共有
P(16,16) = 16! = 16 x 15 x 14 x ..... x 2 x 1   種排列方式

如果 16 樣東西任取兩樣排列,那麼共有

P(16,2) = 16! / (16-2)! = 16 x 15   種排列方式

如果 16 樣東西任取兩樣組合,那麼共有

C(16,2) = 16! / [(16-2)!  x 2!] = 16 x 15 / 2   種組合方式

好,到此為止,這些都是大家從學校習得的數學知識,套公式計算排列組合數值。

最近我跟朋友們開始研究 OEIS A276449 數列 (旋轉碰碰棋),它是個組合問題,這題 Andy 有興趣參與,因此我請他計算 C(16,2),結果他給我一個算式 = 15 + 14 + 13 + ... + 2 + 1 = 120 ?! 答案與階乘計算法結果一樣,因為小朋友才國中而已,我也不主動指導他數學,通常丟有趣問題讓他思考,所以他是有能力解同齡程度的難題,也常自創奇怪解法,這個連加計算就是他自創算法,問為何這麼解?他說十六顆棋子,任意取兩子的組合,相當於選定一顆子後,將剩餘棋子數量遞減相加到一為止,它代表 16 顆選定一個後剩 15 顆可以選,再選定一顆後剩 14 顆可選,以次類推至沒棋子為止,他的解釋我實在想不出邏輯關聯性,不過還是以小朋友的方法驗算比較,結果發現 C(m,2) = m! / [(m-2)! x 2!] = m x (m-1) / 2 = (m-1) + (m-2) + ... + 2 + 1 完全相符。不知道各位讀者還有沒有其它合適的解釋,可以講通為什麼可以遞減連加?講得通就可以稱為 Andy 算法之類,哈哈哈。

這個遞減連加法,只適用任取兩個的組合,取三個以上的計算就不適用,倒是小朋友的算式給我靈感,
m 物任取二個組合像是在計算三角形面積,任取三個組合像是在計算三角錐體積,以下面為例
C(16,2) = 16 x (15/2) 16 為寬,15 為長的三角形
C(16,3) = 16 x (15/2) x (14/3) 16 為寬,15 為長,14 為高的三角錐
那任取四個、五個呢? 我覺得這應是第四度、第五度空間的錐形體
也就是數學組合公式,它與高維空間的特定錐形體是有個對應關係
另外,四維錐形體積就是底部 x 高度 / 4,五維錐形體積就是底部 x 高度 / 5,其餘以此類推,稱這為 Bridan 猜想,因為我沒有能力寫出對應的數學式以及證明,只好稱為猜想,留給數學專家證明之。

我真的想知道歷史上是那一位數學家,發現階乘計算的排列組合公式,也就是 P(m,n) 及 C(m,n) 是誰創建的?以及它對應於多維空間計算,不知道有沒數學家想過這樣的關係?

無論未來結果如何,這是 Andy 在今年爸爸節,送給我最好的禮物。

================================================================
後記,寫完前文後,小朋友又發現告訴我三維解法,舉例說
C(16,3) = 2 x (1x14 + 2x13 + 3x12 + 4x11 + 5x10 + 6x9 + 7x8) = 560
C(m,3) = 1x(m-2) + 2x(m-3) + ..... + (m-3)x2 + (m-2)x1 = m! / [(m-3)! x 3!]
真是神奇啊 !!

================================================================
這篇文章在發文前兩天先給網友 z423x5c6 試閱,並請教小朋友的神奇算式的意義何在,他畫龍點睛後,我才恍然大悟這兩個算式的推導,把他的評論原文張貼如下: Andy 在國中已經有 double counting 的概念真的很厲害!所謂 double counting,就是用兩種有系統的方法數同一個集合內的元素,Andy 所用的方法,如果把棋子加上編號,可能能更好地解釋: 先把棋子編上1 至16 ,再數所有可能的數對,為免重複,規定數對的第一個數必小於第二個數: 有1 的數對有:(1,2) ; (1,3) ; ... ; (1,15) 15 對 2:(2,3) ; ... ; (2,15) 14 對 ...... 14:(14,15) 1 對 數對=15+14+...+1 其實對於取三個也有類似的求和方法,也是來自 double counting 的概念,這裡有一個小小的挑戰給你:試證明 C(m,3)=((m-2)+(m-3)+...+1)+((m-3)+(m-4)+...+1))+...+(3+2+1)+(2+1)+1

29 則留言:

  1. http://imgur.com/set92dQ
    證明有點冗長,期待有更簡短的

    回覆刪除
  2. Bridan猜想是對的!
    http://www.physicsinsights.org/pyramids-1.html
    http://www.sjsu.edu/faculty/watkins/npyramid.htm

    hyperpyramid,暫譯「超錐體」
    但是可能要再修一下,在高維空間(四維以上)中,尚有些中文名詞還沒有翻譯,可以用英文來表示。

    回覆刪除
  3. 哇!西瓜真是很會找資料,已經有專家思考過這問題。
    另外,連證明也自己試看看,真的超厲害,好像在網路上捕獲 大蔥鴨 神奇寶貝!(樂)

    回覆刪除
  4. http://imgur.com/a/om75n
    我試著做了證明,不知猜想內容是不是這個意思?

    回覆刪除
    回覆
    1. 是的,它充分表達我的猜想意思,非常謝謝你。
      建議你再加個二維、三維的圖,甚至四維的圖(如果畫得出來),這應該很值得當作你的科展作品。
      另外,網路發表作品皆有受到著作權法保障,在你完成作品當時就開始生效,如果你不期望作品被任意散佈或拷貝,那就要清楚宣告你的授權範圍及方式,給你參考。

      刪除
    2. 可是既然已成定理,那我還可以以我的名義作科展嗎?
      要以我的名義做科展,要先得到您的授權,所以我還是先確認一下好......。

      刪除
    3. 授權你使用於科展不成問題,通常論文經常擷取他人文章內容,只要是合理使用是 OK 的,也就是標示資料來源,拷貝複製不超過過多比例。基本上,我是採 CC-BY-NC-SA 3.0 協議授權,不要商業使用即可。

      當然遇到作者宣告嚴禁複製散佈的,那就是不能抄。

      刪除
  5. 回覆
    1. 哈,老師也給出一個神奇算式,真是厲害!

      刪除
    2. C(8,3) = 8 x (5+2) = 2 x (1x6 + 2x5 + 3x4) = 56

      看來老師的方法計算量很少,不過其它通式還要再研究。

      刪除
    3. C(3n+1,3) = Σ[3i+1](i=0 to n-1) x (3n+1)
      C(3n+2,3) = Σ[3i+2](i=0 to n-1) x (3n+2)
      C(3n,3) = Σ[3i+1](i=0 to n-1) x (3n-2)

      刪除
    4. 讚!比對了一下,應該沒錯,感覺這還可以再簡化。

      刪除
    5. C(3n,3) = Σ[3i](i=0 to n-1) x (3n) + n
      最後多出來的[+n]有些突兀,因前兩條都沒有。

      刪除
    6. C(n,3) = k * n + p
      k = (n-3) + (n-3-3) + ... + i,(需要 i > 0)
      若i = 1 或 2,則 p = 0;
      若i = 3,則 p = n / i

      刪除
  6. 做了一些整理跟證明。
    https://drive.google.com/file/d/0Bzpp9mO8akXXSW9sS3ZZUVBNWTQ/view?usp=sharing

    回覆刪除
    回覆
    1. 高手在民間,謝謝補充豐富內容,很高興能認識你。

      刪除
    2. 第三頁下半部到第四頁上半確實看不太懂,請問跟我那個式子是用的一樣的方法嗎?

      刪除
    3. 老師的概念並未出現在第三頁證明式中,你的是另外的計算方法,我也很好奇老師的方法,除了 C(m,n), n=3 之外,其它 n 是否也有類似特性,如果有,那應該是一個數學大發現。

      刪除
    4. 其它n應不具有此特性,因這種方法設計初衷只為解決n=3的問題。
      有心人可深究。

      刪除
    5. 廖先生的留言遺失了,補貼如下

      第三頁下半到第四頁上半那一段(即三元和等式),只是按照前一節的方法再做一次分解,然後再將前一節的結果帶入。就是基於此種做法我才認為可以無限拓展。順帶一提,乘積等式或許也可以無限拓展,因為我有想到邏輯解,只是有點難解釋,故沒有打出來,也未多作深究。
      flyingdusts的等式我還沒仔細看,可以問一下是怎麼做出來的嗎? 
      ==========================
      flyingdusts等式,我舉例說明
      C(7,3)=7*(4+1)
      C(8,3)=8*(5+2)
      C(9,3)=9*(6+3)+3=7*(7+4+1)
      看高手能否指點迷津

      刪除
    6. 感恩。
      我看得懂如何計算,我是指如何發現這樣規則的?

      刪除
    7. 這就需要請 flyingdusts 說明,我也很好奇 ^_^

      刪除
    8. 目前在研究科展主題,發現與三角形數(2-單體數)、三角錐數(3-單體數)、和五胞體數(4-單體數)...形成的數列有關係。
      組合「n個取r個的組合數」要對應到體積(面積、超體積...),初步構想是將一個組合對應到1立方單位。

      刪除
    9. 不錯,即將開學了,你可以把科展構想問問老師,老師應該會幫你注意比賽資訊以及提供其它建議,祝你新學年有不錯的成績。

      刪除
    10. 昨天臨近下班,打了不少字,但因一次誤操作全部不見,心痛之下關機走人。
      正如我之前所說,這個規則是設計出來的,而不是發現。
      方法如下:
      已知組合數計算公式C(n,3) = n*(n-1)*(n-2)/(3*2*1)
      先拆出n/1,剩下(n-1)*(n-2)/(3*2);
      受andy的算式啓發,想到構造等差數列,
      [附其求和公式:(首+末)*(末-首+差)/(2*差)]
      以此與上述所剩之式比較,得出差為3;
      故構造末為n-3,公差為3之等差數列,則首有如下3種情形;
      其一,當首為1時,
      (首+末)*(末-首+差)=(1+n-3)*(n-3-1+3)=(n-2)*(n-1),恰為所需;
      其二,當首為2時,
      (首+末)*(末-首+差)=(2+n-3)*(n-3-2+3)=(n-1)*(n-2),恰為所需;
      其三,當首為3時,*
      (首+末)*(末-首+差)=(3+n-3)*(n-3-3+3)=n*(n-3)=n*n-3*n,雖不為所需,
      但從整體看,n*n*(n-3)相較于n*(n-1)*(n-2)=n*n-3*n+2只少一常數,故補上p=n/i。
      (其三證明有誤,但沒吃午餐暫時看不出來問題在哪,待吃完回來再補。)

      刪除
    11. 老師能設計出公式不簡單,沒想到一個排列組合公式,竟然內藏這麼多神奇的東西。

      刪除
    12. Bridan,開句玩笑地說,你收到的這個禮物能為望月教授指路啊,哈哈。

      刪除
    13. 老師指的是望月新一教授?如果這篇文章及討論能跟 ABC 猜想有關聯,那就更神奇了 \^_^/

      刪除