Research Space for Linear Algebra & Discrete Mathematics
1. 那個公式只是把排容的精神再做一下推廣而已, 如果你覺得很難接受的話, 例29那題我是有另一個想法, 但還是用排容:(a)小題先討論其中一種連續的情形如下: 假設 S,R,T 為連續出現的 pair, 這裡要算的是 I,U 皆不連續出現的方法數設a1,a2分別表示出現連續 I,U 的性質此時全部的排列數 S_0 = 10!/(2!)^2 (因為I,U各有2個, 所以除以(2!)^2)S_1 = c(2,1)*9!/2! (I,U中有一個被黏在一起)S_2 = 8!則方法數為 N(!a1!a2) = S_0 - S_1 + S_2= 10!/(2!)^2 - 2*9!/2! + 8!因為 S,R,T,I,U 中任取三個作為連續的pair共有c(5,3)種可能, 所以總方法數就是 c(5,3)*(10!/(2!)^2 - 2*9!/2! + 8!) (b)小題就留給你了2. 5 個連續 0 的方法數這題用遞迴會比較好想令 a_n 為長度為n且具有5個連續0的bit string的個數, a_0=a_1=a_2=a_3=a_4=0, a_5=1當 n>5 時有以下幾種case:1. 若字串中的最後一個1出現在最後一個bit, 會有a_(n-1)種符合的字串2. 若最後一個1出現在倒數第二個bit => a_(n-2)種3. 若最後一個1出現在倒數第三個bit => a_(n-3)種4. 若最後一個1出現在倒數第四個bit => a_(n-4)種5. 若最後一個1出現在倒數第五個bit => a_(n-5)種6. 若前最後五個bit都是0 => 2^(n-5)種所以 a_n = a_(n-1)+a_(n-2)+a_(n-3)+a_(n-4)+a_(n-5)+2^(n-5)=> a_6 = 3 => a_7 = 8=> a_8 = 20=> a_9 = 48=> a_10 = 112
張貼留言
1 則留言:
1. 那個公式只是把排容的精神再做一下推廣而已, 如果你覺得很難接受的話, 例29那題我是有另一個想法, 但還是用排容:
(a)小題先討論其中一種連續的情形如下:
假設 S,R,T 為連續出現的 pair,
這裡要算的是 I,U 皆不連續出現的方法數
設a1,a2分別表示出現連續 I,U 的性質
此時全部的排列數 S_0 = 10!/(2!)^2
(因為I,U各有2個, 所以除以(2!)^2)
S_1 = c(2,1)*9!/2! (I,U中有一個被黏在一起)
S_2 = 8!
則方法數為 N(!a1!a2) = S_0 - S_1 + S_2
= 10!/(2!)^2 - 2*9!/2! + 8!
因為 S,R,T,I,U 中任取三個作為連續的pair共有c(5,3)種可能, 所以總方法數就是
c(5,3)*(10!/(2!)^2 - 2*9!/2! + 8!)
(b)小題就留給你了
2. 5 個連續 0 的方法數這題用遞迴會比較好想
令 a_n 為長度為n且具有5個連續0的bit string的個數,
a_0=a_1=a_2=a_3=a_4=0, a_5=1
當 n>5 時有以下幾種case:
1. 若字串中的最後一個1出現在最後一個bit,
會有a_(n-1)種符合的字串
2. 若最後一個1出現在倒數第二個bit => a_(n-2)種
3. 若最後一個1出現在倒數第三個bit => a_(n-3)種
4. 若最後一個1出現在倒數第四個bit => a_(n-4)種
5. 若最後一個1出現在倒數第五個bit => a_(n-5)種
6. 若前最後五個bit都是0 => 2^(n-5)種
所以 a_n =
a_(n-1)+a_(n-2)+a_(n-3)+a_(n-4)+a_(n-5)+2^(n-5)
=> a_6 = 3
=> a_7 = 8
=> a_8 = 20
=> a_9 = 48
=> a_10 = 112
張貼留言