推 snoopy0907 :你的解法觀點好奇特..試著理解中XD 01/04 16:01
推 springman :這個做法很漂亮...，遞迴公式出來後，也可以一路算.. 01/04 16:10
設r位數的五元序列寒有偶數個1的序列一共有A_r個
則考率此r位數列的第1位數可能為 0 ~ 4
case 1 : 若為 0 , 2 , 3 ,4
則有4 * A_(r-1)種可能
case 2 : 若為 1 , 則後 r-1 位數必須包含奇數個1
則有 ( 5^(r-1) - A_(r-1) ) 種可能
故
A_r = 4 *A_(r-1) + ( 5^(r-1) - A_(r-1) )
= 3 * A_(r-1) + 5^(r-1)
其linear homogeneous解為 c*3^r , non-homogeneous解為 1/2 * 5^r
所以A_r = c*3^r + 1/2 * 5^r
又 A_1 = 4 => c = 1/2
故 A_r = 1/2 * 3^r + 1/2 * 5^r = 3^r + 1/2 * ( 5^r - 3^r )
※ 引述《snoopy0907 (我是男的喔~^0^")》之銘言：
: 一直想不通...能否能請前輩指點一下
: 題目：
: 有r位數的五元序列（0~4）
: 請問含有幾個偶數個1的序列
: （原文 the number of r-digit quintary sequences that
: contain an even number of 1s. What is the total number of
: r-digit quintary sequences with an even number of 1s?)
: 答案：
: 3^r + 1/2 * ( 5^r - 3^r )
: 想法：
: 我不懂的是為什麼前面還要加3^r
: 全部是5^r 減去只有包含2 3 4這些數字的序列
: 不就代表剩下的一定有包含0或1
: 在把它分成兩堆 234位置固定的但0和1不同的分堆
: （ex 222xx33x4xxx x是0或1 ）
: 所以我的想法是 1/2 * ( 5^r - 3^r )
: 不懂為什麼還要加3^r 先謝謝了
因為只包含有234這個的 裡面沒有1呀 所以也是偶數個 :p
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.111.149