Re: [理工] 離散 排列組合
: 例題９想不通 覺得怪怪的
: 另外就是解答可以拆成(4^n)/2+(2^n)/2
: 所以我還想請問這題的解答是不是能另外解釋成比較容易理解的想法？
--
首先考慮，只由0或1所組成，長度為n的序列，且n≧1。
我們可以得到:
含偶數個0的序列數 會等於 含奇數個0的序列數。
--
回到原題，並且 只考慮必定含0或1的四元序列。
^^^^^^^^^^
我們也可以得到:
含偶數個0的序列數 會等於 含奇數個0的序列數。
--
所以，只考慮必定含0或1，且偶數個0的四元序列，
^^^^^^^^^^^^^^
其種數為 必含0或1的四元序列數 的 一半。
即 1/2 * ( 所有四元序列數 - 只含2或3的序列數 )
= 1/2 * (4^n - 2^n)
再加上剩下的部分: 不含0與1，即只含2或3的序列數
1/2 * (4^n - 2^n) + 2^n = (4^n + 2^n)/2
--
這題常見的解法有: 指數生成函數, 遞迴式。
以下提供另一種解法。
含 0個0 的四元序列個數: 3^n = C(n,n) * 3^n
2個0 : C(n,2) * 3^(n-2) = C(n,n-2) * 3^(n-2)
4個0 : C(n,4) * 3^(n-4) = C(n,n-4) * 3^(n-4)
6個0 : C(n,6) * 3^(n-6) = C(n,n-6) * 3^(n-6)
... ... .... = ... ....
+)____________________
If n is even, 3只有偶數次方
C(n,n)*3^n + C(n,n-2)*3^(n-2) + C(n,n-4)*3^(n-4) + ...
+ C(n,2)*3^2 + C(n,0)*3^0
= [(1+3)^n + (1-3)^n]/2
= (4^n + 2^n)/2
If n is odd, 3只有奇數次方
C(n,n)*3^n + C(n,n-2)*3^(n-2) + C(n,n-4)*3^(n-4) + ...
+ C(n,3)*3^3 + C(n,1)*3^1
= [(1+3)^n - (1-3)^n]/2
= [4^n - (-2)^n]/2
= (4^n + 2^n)/2
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.139.236
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508172292.A.C19.html
推
10/17 01:51,
6年前
, 1F
10/17 01:51, 1F
→
10/17 01:53,
6年前
, 2F
10/17 01:53, 2F
感謝提醒
再補充一個奇偶數不用分開考慮的版本
含 0個0 的四元序列個數: 3^n = C(n,0) * 1^0 * 3^n
2個0 : C(n,2) * 3^(n-2) = C(n,2) * 1^2 * 3^(n-2)
4個0 : C(n,4) * 3^(n-4) = C(n,4) * 1^4 * 3^(n-4)
6個0 : C(n,6) * 3^(n-6) = C(n,6) * 1^6 * 3^(n-6)
... ... .... = ... ....
2*m個0 : C(n,2*m) * 3^(n-2*m) = C(n,2*m) * 1^(2*m) * 3^(n-2*m)
+)_____________________________
where m = floor(n/2)
觀察發現，1只有偶數次方。
C(n,0) * 1^0 * 3^n + C(n,2) * 1^2 * 3^(n-2) + C(n,4) * 1^4 * 3^(n-4) + ...
+ C(n,2*m) * 1^(2*m) * 3^(n-2*m)
= 1/2 * [ (3+1)^n + (3-1)^n ]
= (4^n + 2^n)/2
※ 編輯: JKLee (118.161.200.52), 10/17/2017 16:35:51
討論串 (同標題文章)
