推 phonya : 懂了！感謝你～ 03/25 14:14
推 cutekid : 學習+1 03/25 16:35
※ 引述《phonya (楓夜)》之銘言：
: Q：將編號1到10的球分成甲乙丙三堆，每堆至少一顆球，且相鄰數字不在同一堆，請問共有
: 多少種分法？
: A：1530種
: 題目來自106身障甄試數乙考題
: 只能想到每組至多5球可以縮減討論範圍…
: 但還是想不到怎麼解決orz
用遞迴的想法去解
3個球的情況
每堆 1 顆，總共3! = 6 種
4個球的情況
每種 3球的狀態，要再加入4號球都有2種選擇（只要不要放入3號球所在的組別就行）
但還有一類合法的狀態是沒辦法從上述3個球的情況再加入一顆球衍生的
那就是4號球單獨一堆，1,2,3號球在剩下兩個組別的情形
由於連續號碼不能相鄰的關係，只能1,3一組 ，2 一組
這個關係不只是n=4的時候成立
n=5，5號球單獨一堆的時候，剩下的1,2,3,4號球也只有唯一的一種分組
（即 1,3 一組 2,4一組）
考慮甲乙丙排列的話，這類的組態共有6種
所以我們可以知道
a_n+1 = a_n *2 + 6
a_3 = 6
a_4 = 18
a_5 = 42
a_6 = 90
a_7 = 186
a_8 = 378
a_9 = 762
a_10= 1530
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.189.237 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1648187602.A.CF4.html