※ 引述《TOOYA (在草地等流星)》之銘言： : ※ 引述《vvbird (vv)》之銘言： : : 用 A、B、C、D、E、F 六個字母形成一個 9 個字母的單字 : : 至少出現一組三個連續字母 BAD 的機率為何? : :(恕刪) : ----------------------------------------------------------------------- : 剛想了一下 這裡的排容又跟之前的不是完全一樣 這裡沒有三個圈圈(AUBUC之類) : 我在這裡解釋一下 : ┌───┬───┬───┬───┬───┐ : │ │ 沒有 │ 恰一 │ 恰二 │ 恰三 │ : ├───┼───┼───┼───┼───┤ : │ 任意 │ ˇ│ ˇ│ ˇ│ ˇ│ : ├───┼───┼───┼───┼───┤ : │ 一組 │ │ ˇ│ ˇˇ│ˇˇˇ│ : ├───┼───┼───┼───┼───┤ : │ 二組 │ │ │ ˇ│ˇˇˇ│ : ├───┼───┼───┼───┼───┤ : │ 三組 │ │ │ │ ˇ│ : ├───┼───┼───┼───┼───┤ : │ +-+- │ ˇ│ │ │ │ : └───┴───┴───┴───┴───┘ : ˇ個數表在這個計算[Ｎ組(以上)]下，恰Ｎ被算到的次數 : 一組的情形 有 B A D _ _ _ _ _ _ : _ _ _ B A D _ _ _ : 它將恰二中的 B A D B A D C E F 計算了兩次 所以在一組x恰二的空格記作ˇˇ : 一組的情形 有 B A D _ _ _ _ _ _ : _ _ _ B A D _ _ _ : _ _ _ _ _ _ B A D : 它將恰三中的 B A D B A D B A D計算了三次 所以在一組x恰三的空格記作ˇˇˇ : 其他就類推吧 所以用萬用暴力討論法(笑)時，倒著想比較快 Note That: 恰Ni組 與 恰Nj組 在 i=\=j 時為 互斥事件，故計算完洽N組可直接加總不 用考慮 恰三組 BADBADBAD → 一種 恰兩組 BAD---BAD (類數)*{(所有排法)-(此位子下出現恰三組)} BADBAD--- 共三類 → 3 * ( 6*6*6 - 1 )= 645 ---BADBAD BAD-BAD-- --BAD-BAD BAD--BAD- (類數)*{(所有排法)-(此位子下出現恰三組(不可能))} -BAD--BAD 共七類 → 7 * ( 6*6*6 - 0 )= 1512 -BADBAD-- --BADBAD- -BAD-BAD- (用3H3=10知恰兩組共十類BAD分配法) 恰一組 BAD------ (類數)*{(ALL)-(此位子恰兩組(對照上面)-(三組) ) ------BAD 此兩類 → 2 * (6^6 - (2*(6^3)+2*(6^3-1)) - 1)= 91586 -BAD----- -----BAD- 此兩類 → 2 * (6^6 - (3*(6^3)) - 0)= 92016 --BAD---- ----BAD-- 此兩類 → 2 * (6^6 - (2*(6^3)) - 0)= 92448 ---BAD--- 此一類 → 1 * (6^6 - (2*(6^3-1)) - 1)= 46225 (2H6=7沒有其他類) Total= 324433 (訂正之前計算錯誤) 324433 P=Total/6^9= -------- ~= 0.0321932 = 3.21932% 10077696 其實暴力法沒我想像的慢...... 以上，有問題請不吝指教。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.166.198.243 ※ 編輯: Peter1986110 來自: 218.166.198.243 (05/05 17:16) 抱歉!是我想錯了，T大的算是對的!已刪掉錯誤想法，另外之前計算錯誤，更正後機率一樣 注:T大算式小改:(2H6)*6^6 - (3H3)*6^3 + 1 = 324433 (其實除了7跟10可以用H來算不用慢慢窮舉以外沒變) ※ 編輯: Peter1986110 來自: 218.166.198.243 (05/06 00:53) 無聊?我的確是無聊到想要一般化這個問題才搬出H: 排n個，有m種，給定完全不自重複字串k個字(之所以說不自重複像規定這種字串:BADBA因 為字串有自重複會導致BADBA---在填BAD就算重複兩次)，問至少出現一次之機率 用排容&手算只能做到: (手數)m^(n-k)-(手數)*m^(n-2k)+(手數)*m^(n-2k)-...+......../m^n 不手算而用 H or C or whatever 公式算出幾組特殊字串排法種類數 就很清楚是: (2H(n-k))m^(n-k)-(3H(n-2k))*m^(n-2k)+.../m^n 其中第t項為: (-1)^(t+1)*[(t+1)H(n-tk)]*m^(n-tk) 尾項之t為 t=t0 s.t. n-tk<k i.e. 通式為:(n=字串長,m=字種類,k=特定不自重複字串長) t P(至少出現一次字串)=[Σ (-1)^(i+1)*[(i+1)H(n-ik)]*m^(n-ik)]/m^n i=1 其中 t=min[{t|n-tk<k,t屬於自然數}] 對不起，我不太懂ph大的意思，可否詳述之? ※ 編輯: Peter1986110 來自: 218.166.192.105 (05/07 23:14) 我那個時候趕出門隨便算算你也要鞭...... 我暴力算並非我的本意，但是想算算看暴力算法在可用計算機的情況下有多難算才算的 老實說，我只是想要討論這個問題而已，因為我對這個問題的一般化有興趣，T大之前所言 亦讓我受惠良多，但我不懂得T大為何要如此惡言相向?假如你覺得我的用語讓你情感上有 不悅之處，那我道歉，假如我在學問上有所不足，那還請你多多指教 但假如你質疑我nHm的用法有錯，請證明我下面的論述是錯誤的，畢竟數學的方法要用數學 解決: Q:對一個特定字串長k，重複取m種字排n長度字串，在特定字串長k重複t次的種類數 pf: 考慮 特定字串 特定字串 .....t個特定字串(共kt個字已填) ^ ^ ^ t+1個可填其他字的位置 剩下n-kt字可以填在這t+1個位置 即為特定字串視為符號A(t個)，其他字元視為符號B(n-kt個)之直線排列 故有(t+n-kt)!/t!(n-kt)!種可能，亦等於(t+1)H(n-kt)種可能 // ----- 我的確很無聊，我現在在思考的是不考慮迴文視為同字串情況下，有哪些情況會導致那個 一般式掛掉?(雖然我知道T大對我的公式存疑，但在我自己實驗下我還看不到反例，同時我 也還看不出我的證明那裡有問題)，以及所有會讓我的一般式掛掉的狀況是否亦有自己的一 般解，現在已知指定一自重複(如AA、BABA)、或部分自重複字串(如BAB、BACB)會出事，想 找一般解中...... ※ 編輯: Peter1986110 來自: 61.231.24.163 (05/09 13:37)