Re: [解題] 高二數學-組合+遞迴
※ 引述《sarsenwen (超囧學生 衝阿!)》之銘言：
: 1.年級：二年級
: 2.科目：數學
: 3.章節：排列組合跟遞迴綜合
: 4.題目：有一n*1塊的長方形空格 (n為自然數)
: 現在有2種貼紙 一種是白色的1*1 另一種是黑色的3*1
: 設定A(n)為此長方形可以有幾種貼法
: 例 A(1)=1 A(2)=1 A(3)=2 A(4)=3 ......
: 問一般式 A(n)=?
: 5.想法：基本上我把A(1)~A(12)都算了出來
: 依序是：1 1 2 3 4 6 9 13 19 28 41 60
: 還真的看不出前後項有什麼關係...
: 這題是學生學校發的考卷上的題目 目前還沒有解答
---
假設 白色貼紙有 a 個 , a、b 屬於 {N,0}
黑色貼紙有 b 個
可知
A(n) = Σ C(a+b,a) , 滿足 3a+b=n
(a,b)
[n/3]
= Σ C(n-2a,a) ____(1)
a=0
例如當 n=12
(a,b) = (0,12) 、 (1,9) 、 (2,6) 、 (3,3) 、 (4,0)
所以 A(12) = C(12,0) + C(10,1) + C(8,2) + C(6,3) + C(4,4)
= 1 + 10 + 28 + 20 + 1
= 60
----
以高中生來說
能寫出 (1) 式就已經夠了
但若要寫出 A(n) 對 n 的 closed form
這有點超出高中數學的範疇 (大學的 離散數學 或 線性代數 有一套標準解法)
因為不是所有的遞迴都可以寫出 A(n) 的 closed form
( 這題有辦法寫，但我不打XD )
所以
用組合數來代表通解會變成是另一種常見的手段
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
推
05/31 08:44, , 1F
05/31 08:44, 1F
推
05/31 08:52, , 2F
05/31 08:52, 2F
→
05/31 08:54, , 3F
05/31 08:54, 3F
推
05/31 17:13, , 4F
05/31 17:13, 4F
討論串 (同標題文章)