2013年8月3日 星期六

Hints on Total 22

http://4rdp.blogspot.com/2013/08/hints-on-total-22.html

總和二十二的組合難題，難度很高，這裡提供線索，留給高手回答。

舉例來說，整數 4，有八種排列組合 (Composition) 方式， 4,  3+1,  2+2,  1+3,  2+1+1,  1+2+1, 1+1+2,  1+1+1+1。如果限制同類型不重複 (Partition) 則有五種：4,  3+1,  2+2,  2+1+1, 1+1+1+1。

各位可以參考
OEIS 資料庫 A000079 (Composition)，A000041 (Partition) 的說明。

在求解這題問題時，有發現一個新數列 a(n) = a000079(n) + a000041(n)，不過缺乏數學意義，而被 OEIS 拒絕發表，在此徵求可以給予意義的人聯名發表。

標籤：

2 則留言:

  1. Unknown2016年1月7日 晚上9:06

    對於可重覆的方法數，我的想法是：
    最左邊的數可能是1，也可能是2，…，也可能是10。
    所以若令加起來的數是k時的分法共有N(k)種方法 (可重覆，即10, 10, 2 與 10, 2, 10看作不同分法)
    則n(k)=n(k-1)+ n(k-2)+ n(k-3)+ n(k-4)+ n(k-5)+ n(k-6)+ n(k-7)+ n(k-8)+ n(k-9)+ n(k-10)
    故所求=n(22)
    =n(21)+ n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12)
    =2(n(20)+ n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+n(11)
    =4(n(19)+ n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+3n(11)+2n(10)
    =8(n(18)+ n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+7n(11)+6n(10)+4n(9)
    =16(n(17)+ n(16)+ n(15)+ n(14)+ n(13)+ n(12))+15n(11)+14n(10)+12n(9)+8n(8)
    =32(n(16)+ n(15)+ n(14)+ n(13)+ n(12))+31n(11)+30n(10)+28n(9)+24n(8)+16n(7)
    =64(n(15)+ n(14)+ n(13)+ n(12))+63n(11)+62n(10)+60n(9)+64n(8)+48n(7)+32n(6)
    =128(n(14)+ n(13)+ n(12))+127n(11)+126n(10)+124n(9)+120n(8)+112n(7)+96n(6)+64n(5)
    =256(n(13)+ n(12))+255n(11)+254n(10)+252n(9)+248n(8)+240n(7)+224n(6)+192n(5)+128n(4)
    =512n(12)+511n(11)+ 510n(10)+508n(9)+ 504n(8)+ 496n(7)+ 480n(6)+ 448n(5)+ 384n(4)+256n(3)
    =1023n(11)+ 1022n(10)+ 1020n(9)+ 1016n(8)+ 1008n(7)+ 992n(6)+960n(5)+ 896n(4)+ 768n(3)+ 512n(2)
    = 2045n(10)+ 2043n(9)+ 2039n(8)+ 2031n(7)+ 2015n(6)+1983n(5)+ 1919n(4)+ 1791n(3)+ 1535n(2)+1023n(1)
    =4088n(9)+ 4084n(8)+ 4076n(7)+ 4060n(6)+4028n(5)+ 3964n(4)+ 3836n(3)+ 3580n(2)+3068n(1)
    =8172n(8)+ 8164n(7)+ 8148n(6)+8116n(5)+ 8052n(4)+ 7924n(3)+ 7668n(2)+7156n(1)
    =16336n(7)+ 16320n(6)+16288n(5)+ 16224n(4)+ 16096n(3)+ 15840n(2)+15328n(1)
    =32656n(6)+32624n(5)+ 32560n(4)+ 32432n(3)+ 32176n(2)+31664n(1)
    =65280n(5)+ 65216n(4)+ 65088n(3)+ 64832n(2)+64320n(1)
    =130496n(4)+ 130368n(3)+130112n(2)+129600n(1)
    =260864n(3)+260608n(2)+260096n(1)
    =521472n(2)+520960n(1)
    =1042432n(1)
    =1042432

    所以共有1042432 方法。

    回覆刪除
    回覆
    1. Bridan2016年1月7日 晚上11:34

      這題放了近兩年半，終於有人提出"重複"的解法，不過正解要計算到 n(0),2083841
      雖然少算一個步驟，方老師還是很厲害，從看到題目到寫出解法不到一天的時間，我還沒有這樣的功力

      刪除

訂閱： 張貼留言 (Atom)