作者CMJ0121 (请多指教!!)
看板Grad-ProbAsk
标题Re: [理工] [离散]-递回
时间Mon Dec 28 18:29:11 2009
※ 引述《yesa315 (XD)》之铭言：
: 求一 n-digit 数字串列由 0,1,2,3组成 含偶0且偶1的有几种? 请用递廻
: 用生成函数来看 我一下就想出来了
: 用递廻观念 有点卡卡的
: 另An为解
: 1.首项 =\= 0,1 方法数 2A(n-1)
: 再来就卡了
: 请高手指导
: 谢谢
我来挑战看看 = =
先给定 n-digit
step 1.
把 {0,1}, {2,3}看成两个个体
则{0,1}各有 1/2的机会总数为偶数/奇数
假设{0,1}总数为偶数的情况下
{0}的总数为偶数的机率为1/2
故 {0,1}为奇数的可能性 = 2*{0,1}为偶数且{0}{1}也为偶数
step 2:
故我们知道 在 {0,1}为奇数的情况下, 只要在加上特定的 {0,1}
就可以得到 {0},{1}皆为偶数的情况 ---- 情况1
且在 {0},{1}皆为偶数的情况下 只要加上任意的 {2},{3}
依然可以得到{0}{1}皆为偶数 ---- 情况2
故 a_n = 2*a_{n-1} + 2*a_{n-1} = 4*a_n{n-1}
==> a_n = c*2^n
又 a_1 = 1
故 a_n = 2^{n-1} done!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.112.39.42
1F：推 chenbojyh:a4 怎麽可能只有 1 辛苦了 不过答案应该是错的 12/28 18:41
※ 编辑: CMJ0121 来自: 59.112.39.42 (12/28 19:00)
2F：→ CMJ0121:改过了 刚刚脑残应该是a_1 = 1 12/28 19:01