Re: [中學]排列組合................
※ 引述《adamchi (adamchi)》之銘言
:1.
: _ _ _ _
: l_l_l_l_l
: l_l_l_l_l
: l_l_l_l_l
: l_l_l_l_l
: (上圖為一4*4的圖形，共有16個小正方形
: 每一個小正方形的"對角線"煩請大家自行補上)
: 問 : 上圖共有多少個三角形
: (別忘了裡面每個小正方形要補上對角線再算)
: 2. 青蛙在A,B,C,D四點跳動,每次跳動落點異於跳點
: 若青蛙從A點出發,跳n次後仍回到A點,則跳法數為_______
: 請問 : 令An為跳n次後回到A的方法數
: 為什麼遞迴關係式為 An = 3*A(n-2) + 2*A(n-1)
: (懂3*A(n-2),不清楚的是 2*A(n-1) )
: (PS A(n-2)為 跳n-2次後回到A的方法數 )
因為你第一題不清楚，暫時跳過第一題，沒有想像中難(看邊長去想)
我針對第二題討論
<<我這邊將跳n次捨去，看跳第n次後的狀態>>
係數3想必你也知，因為落點不等於跳點。
所以An的前一個一定是B C D
再往前推也就是A(n-2)，所以是3*A(n-2)種可能
如圖：
跳第k次後位置
次數 n-2 n-1 n
位置 A → B → A
A → C → A
A → D → A
好！這邊你好像想對了，但你忘了再往前的第n-2步完的起跳點不一定是A啊。
怎麼辦？
@@@ 所以要考慮A(n-3)
※※※
先打個插：以下情形雖然違反題目不可能，但會用到A(n-1)，好用！
次數 n-3 n-2 n-1 n
位置 A → X → A → A 其中 X = B, C 或 D 3種情形
<<回到之前>>
因為只要找A(n-3)到A的關係就好。
你所想到的都幫你列出來了
次數 n-3 n-2 n-1 n
位置 A → B → C → A
A → C → B → A
A → D → C → A
A → C → D → A
A → B → D → A
A → D → B → A
你有沒有發現A(n-3)到A(n-1)再到A有3種(這是題目不可能發生的，但好用我們拿來用)
A點在第(n-3)次到非A的其他點，再回到n位置A有6種，
※1224發現這句有錯→※「是A(n-1)的2倍。」
※1224改※ ( 若A在n-3正常跳兩次到n-1步 <=> A(n-1)=3A(n-3)
若A在n-3正常跳三次到 n 步 <=> An=6A(n-3) )
以上是考慮n-3跳的情形！
=> An = 2 A(n-1)
這個"2"也就是我剛剛說的扣掉A點及原跳點(n-2)的。所以你跳到(n-1)只剩下
"2種"選擇。(e.g. n-2 步到 B 後 再走 n-1 步 只剩 C 或 D)
※※※
若原式寫成這樣你一定會懂，就是我剛剛@@@所說的：
An = 3*A(n-2) + "6"A(n-3).........................(X)
※原本"6"忘了寫※
但遞迴式能簡化便簡化，別弄到3層關係。
所以用A(n-3) = (1/3) * A(n-1)代入 (X)式中
得到關係式 An = 3*A(n-2) + 2*A(n-1)
寫了好多，不知你懂了嗎？
這題的關鍵
(1)"An"在於"A"是 起點 亦要是 終點 。
(2)還有Ak， 第k位的前一位絕不能是 A
小弟非學數學本科的，只是個人很喜歡組合數學，希望能幫到你！
wachsend
→ bineapple :跳n-2次後不為A的方法數和跳n-1次後為A的方法數相同 12/23 00:44
B大的講法，就是我所討論的，只是他少說了一句"中間只剩 2 個選擇"
※ 編輯: wachsend 來自: 59.121.157.153 (12/23 01:51)
抱歉！後來發現(X)式寫錯，是An=3A(n-2)+ 6A(n-3)才對
大概是半夜太想睡的緣故吧！還有中間也有錯，已修改了！
※ 編輯: wachsend 來自: 125.227.156.33 (12/24 00:59)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 4 篇)：