X + Y + Z + ... = 22， 0 ＜ X,Y,Z, ... ≦ 10
難度 ✩✩✩✩
這是我的小朋友不服氣我數學厲害，特別出題考我的暑假作業，並打算考倒全校數學高手，這題我花了很多天時間進行基礎研究，並查閱 OEIS，因粗心計算錯誤以為自己找到新數列，結果白忙一場，如果自認為是數學高手，就接受挑戰吧：
任意正整數排列組合，相加等於 22，並且單一整數最大值為 10，如果 10 + 10 + 2 是一種組合，那麼 10 + 2 + 10 是重覆的組合，請問有多少種排列組合不重覆？如果可以重覆有多少種？
這一題真的是很難，組合不重覆或許你可以慢慢排慢慢算，反正答案在一千以內，但是計算排列可以重覆，沒有利用數列，應該會算到天荒地老！
2013/8: 補充提示。
2016/1: 試算表解法公告，含 "不重複"、"重複" 及董芳成老師解法。
任意正整數排列組合，相加等於 22，並且單一整數最大值為 10，如果 10 + 10 + 2 是一種組合，那麼 10 + 2 + 10 是重覆的組合，請問有多少種排列組合不重覆？如果可以重覆有多少種？
這一題真的是很難，組合不重覆或許你可以慢慢排慢慢算，反正答案在一千以內，但是計算排列可以重覆，沒有利用數列，應該會算到天荒地老！
2013/8: 補充提示。
2016/1: 試算表解法公告，含 "不重複"、"重複" 及董芳成老師解法。
有一條香腸,有22節,中間有21個連接點,
回覆刪除每個連接點,可切,可不切,
全部組合:有2^21次方,
把題目轉換成21位數的2進位數字,或是21位數字串
=========================
題目:最大塊香腸~限制長度10節香腸,可以組合重覆時,
先~~負面思考:
(NG-case1):先切一塊11節香腸時,剩下11節有2^10的組合
(NG-case2):先切一塊12節香腸時,剩下10節有2^9的組合
(NG-case3):先切一塊13節香腸時,剩下9節有2^8的組合
.....
.....
(NG-case12):先切一塊22節香腸時,剩下0節有2^0的組合
所以NG組合共有2^10+2^9+2^8+2^7+...+2^0=(2^11)-1
再回到正面思考:
則(OK組合)=(全部組合:2^21)-(NG組合:2^11-1)
==========================================
但是組合不重覆的狀況,就還沒想到怎麼計算了
自己吐槽自己一下
刪除(NG-case09):先切一塊19節香腸時,剩下3節,有2^2=4的組合
(NG-case10):先切一塊20節香腸時,剩下2節,有2^1=2的組合
(NG-case11):先切一塊21節香腸時,剩下1節,有2^0=1的組合
(NG-case12):先切一塊22節箱腸時,剩下0節,有2^0=1的組合
所以(NG組合)=(2^10)+(2^9)+(2^8)+...+(2^0)+(2^0)=(2^11)-1+1=(2^11)
(OK組合)=(全部組合:2^21)-(NG組合:2^11)
.........
嗯,還是有怪怪的地方
.....抱歉,我再有空再想想
您好，
刪除能用切香腸來比喻這題 總合二十二 數學題，真是傳神貼切，怪怪的地方在最長為十段連結，而非十一段連結。
我是利用試算表幫忙加總計算，沒關係有的是時間慢慢思考，祝你成功求解。
再補充線索，不可重複排列可參考 OEIS A008284，可重複排列的 A048004。
刪除這個問題有人已經給出通解，見
回覆刪除http://blog.chinaunix.net/uid-26548237-id-3503956.html
我放在compileonline上，結果顯示為807
Linke 謝謝你，807 是"不重複"的正解，沒想到有網友早就解決這個問題。
回覆刪除這題的"不重複"通解與數列 A008284 相關，詳見 http://oeis.org/A008284
很佩服你的耐性，逐一克服各式難題，有這樣個性的人，會有成功的一天。
喜歡與你網路交誼，日後有機會去香港或你來台北，和你相聚認識認識。
關於重複組合的解答，大家繼續努力。等有人解答之後，再公佈我的試算表解答。
哈哈，Bridan您過譽啦~
刪除台北我讀書的時候去過一次，那裏濃厚的學習氣氛我十分喜歡.
如果能夠再去的話一定找你~
你要是來香港我也應該好好招待你呀~
這都要歸功於你的博文很有趣，我把其中的幾篇還講給過小朋友們聼呢~
希望你的博客越寫越好~
Linke 隨時歡迎您來，有你們這些讀者的加油，我會更加努力。
刪除目前初步計畫每週兩文，其中一篇有關訓練數學感，先寫到明年底湊一百篇。
對於可重覆的方法數，我的想法是：
回覆刪除最左邊的數可能是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 方法。
這題放了近兩年半，終於有人提出"重複"的解法，不過正解要計算到 n(0),2083841
刪除雖然少算一個步驟，方老師還是很厲害，從看到題目到寫出解法不到一天的時間，我還沒有這樣的功力
更正一下 (沒錯！要算到n(0)):
刪除X + Y + Z + ... = 22， 0 ＜ X,Y,Z, ... ≦ 10
-------
對於可重覆的方法數，我的想法是：
最左邊的數可能是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(0)=1 例如 n(2) 的最左邊的數可能是1或2 所以 n(2)=n(1)+n(0)=1+1=2
也可以直接 n(2)=n(1)+n(0) =n(0)+n(0)= =2n(0)=2 ]
故所求=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)+56n(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)+2045n(0)
=8172n(8)+ 8164n(7)+ 8148n(6)+8116n(5)+ 8052n(4)+ 7924n(3)+ 7668n(2)+7156n(1)+6133n(0)
=16336n(7)+ 16320n(6)+16288n(5)+ 16224n(4)+ 16096n(3)+ 15840n(2)+15328n(1) +14305n(0)
=32656n(6)+32624n(5)+ 32560n(4)+ 32432n(3)+ 32176n(2)+31664n(1) +30641n(0)
=65280n(5)+ 65216n(4)+ 65088n(3)+ 64832n(2)+64320n(1) +63297n(0)
=130496n(4)+ 130368n(3)+130112n(2)+129600n(1) +128577n(0)
=260864n(3)+260608n(2)+260096n(1) +259073n(0)
=521472n(2)+520960n(1) +519937n(0)
=1042432n(1) +1041409n(0)=2083841
(謝謝Bridan的指正！)
謝謝方老師予以指導，說真的，我沒想到用這種解法，只會苦力的用試算表總計，不然當時就可以很快破解小朋友的考題。
刪除