Re: [中學] 分堆問題
※ 引述《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
推
03/25 14:14,
3年前
, 1F
03/25 14:14, 1F
推
03/25 16:35,
3年前
, 2F
03/25 16:35, 2F
討論串 (同標題文章)