查看完整版本 : 組合

elvistsang420 2014-11-19 12:15 AM

組合

有6封信ABCDEF 同信封abcdef
每個信封只可以入一封信
甘6封信都吾會入落自己英文字母既信封總共有幾多個組合呢??例如A 入b,  B 入c......F 入a為之一個組合
小弟不才 還請指教:smile_41::smile_41:[url=http://www.discuss.com.hk/android][img=100,23]http://i.discuss.com.hk/d/images/r10/androidD.jpg[/img][/url]

[[i] 本帖最後由 elvistsang420 於 2014-11-19 12:16 AM 使用[url=http://www.discuss.com.hk/android][img=100,23]http://i.discuss.com.hk/d/images/r10/androidD.jpg [/img][/url] 編輯 [/i]]

[7] 2014-11-19 04:00 AM

[quote]原帖由 [i]elvistsang420[/i] 於 2014-11-19 12:15 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=402779353&ptid=24041982][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
有6封信ABCDEF 同信封abcdef
每個信封只可以入一封信
甘6封信都吾會入落自己英文字母既信封總共有幾多個組合呢??例如A 入b,  B 入c......F 入a為之一個組合
小弟不才 還請指教:smile_41::smile_41:[url=http://i.discus]http://i.discus[/url] ... [/quote]
我先把問題變成general  case(希望一陣你明點解我會化簡為繁),再教你做這一個particular case。

即現有n封信a_1,a_2....a_n,及n個信封A_1,A_2,....A_n,其他要求目標等完全一樣。
設我們要求的組合數為[img]http://latex.codecogs.com/gif.latex?Q_n[/img]。
其中[img]http://latex.codecogs.com/gif.latex?Q_0=1[/img],[img]http://latex.codecogs.com/gif.latex?Q_1=0[/img](why?)

如果沒有每封信都不能落入自已英文字母的規定,那麼這個答案很明顯,就是n!,即n個排列數(why?)
所以,答案[img]http://latex.codecogs.com/gif.latex?Q_n[/img]應該[img]http://latex.codecogs.com/gif.latex?=n!-[/img](不符合規定的組合的數量)
所以,我們現在來檢查一下,這些不符合規定的組合數到底有多少?

首先沒有信符合規定,即其實是每封信都去了自己的信封[img]http://latex.codecogs.com/gif.latex?=1=Q_0C_n^n[/img]。
如果只有一封信符合規定(其實是沒有這個可能的,不過我們也包這個case,一陣u will c),即其實有n-1封信沒有合規[img]http://latex.codecogs.com/gif.latex?=0=Q_1C_{n-1}^n[/img]。
如果只有2封信符合,即有n-2封去了自己的信封[img]http://latex.codecogs.com/gif.latex?=Q_2C_{n-2}^n[/img]。

.....[img]http://latex.codecogs.com/gif.latex?%5Cbg_white%20%5Cput%2850%2C0%29%7Ba_1%7D%5Cput%2850%2C0%29%7Ba_%7B...%7D%7D%5Cput%2850%2C0%29%7Ba_r%7D%5Cput%2850%2C0%29%7Ba_%7Br+1%7D%7D%5Cput%2850%2C0%29%7Ba_%7B...%7D%7D%5Cput%2850%2C0%29%7Ba_n%7D%20%5Cput%28-262%2C-10%29%7B%5Cvector%28-1%2C-1%29%7B50%7D%7D%5Cput%28-200%2C-10%29%7B%5Cvector%28-1%2C-1%29%7B50%7D%7D%5Cput%28-135%2C-10%29%7B%5Cvector%280%2C-1%29%7B50%7D%7D%5Cput%28-68%2C-10%29%7B%5Cvector%280%2C-1%29%7B50%7D%7D%5Cput%28-7%2C-10%29%7B%5Cvector%280%2C-1%29%7B50%7D%7D%5Cput%28-325%2C-10%29%7B%5Cvector%282%2C-1%29%7B100%7D%7D%20%5Cput%28-330%2C-70%29%7BA_1%7D%5Cput%2847%2C0%29%7BA_%7B...%7D%7D%5Cput%2847%2C0%29%7BA_r%7D%5Cput%2847%2C0%29%7BA_%7Br+1%7D%7D%5Cput%2847%2C0%29%7BA_%7B...%7D%7D%5Cput%2847%2C0%29%7BA_n%7D%20%5Cput%28-265%2C-10%29%7B%5Coval%28140%2C10%29%5Bb%5D%7D%5Cput%28-75%2C-10%29%7B%5Coval%28140%2C10%29%5Bb%5D%7D%20%5Cput%28-320%2C-25%29%7Br%20letters%20of%20mismatch%7D%20%5Cput%28-150%2C-25%29%7Bn-r%20letters%20of%20identical%20match%7D[/img]

如是者,如果有n-1封信合規,即有1封信去了自己的情況有[img]http://latex.codecogs.com/gif.latex?Q_{n-1}C_1^n[/img]個。
所以,我們得出

[img]http://latex.codecogs.com/gif.latex?%5Cbg_white%20Q_n%3Dn%21-%28Q_0C_%7Bn%7D%5E%7Bn%7D+Q_1C_%7Bn-1%7D%5E%7Bn%7D+Q_2C_%7Bn-2%7D%5E%7Bn%7D+.....+Q_%7Bn-1%7DC_1%5En%29%5Chspace%7B5pc%7D%281%29%5C%5C%20%24or%24%5C%5C%20%5Cindent%20n%21%3DQ_0C_%7Bn%7D%5E%7Bn%7D+Q_1C_%7Bn-1%7D%5E%7Bn%7D+Q_2C_%7Bn-2%7D%5E%7Bn%7D+.....+Q_%7Bn-1%7DC_1%5En+Q_nC_%7B0%7D%5E%7Bn%7D%5Chspace%7B5pc%7D%5C%21%5C%21%5C%21%282%29[/img]

(2)式我們叫它做difference equation of order n,solve(2)我們就可以得出Q_n的解了,詳細情況,你孤高一下difference equation罷。這一招很普遍的,你再學就要學generating functions...等等,這裡我就不詳說了。

啊!至於你的情況其實可以不那麼複雜的,因為你只係求Q_6。
你只要用(1)式逐個做便算:
Q_0=1
Q_1=0
Q_2=1(why?)
Q_3=3!-(1+0+1x3C1)=2
Q_4=4!-(1+0+1x4C2+2x4C1)=9.....
Q_5=5!-(1+0+1x....+2x.....+9x.....=44.....
Q_6=??
如此類推,其實10以下都不會太難找的.......。
其實[img]http://latex.codecogs.com/gif.latex?Q_n[/img]還有兩個比我剛說的這個更簡單的recurrence relation的,不過其中一個好難諗的,你試下挑戰下。

[[i] 本帖最後由 [7] 於 2014-11-19 11:35 AM 編輯 [/i]]

填不盡 2014-11-19 12:20 PM

*** 作者被禁止或刪除 內容自動屏蔽 ***

elvistsang420 2014-11-19 12:51 PM

可吾可以出埋個答案  我計到個數但係吾知岩吾岩



[url=http://www.discuss.com.hk/android][img=100,23]http://i.discuss.com.hk/d/images/r10/androidD.jpg[/img][/url]

[7] 2014-11-19 01:28 PM

[quote]原帖由 [i]elvistsang420[/i] 於 2014-11-19 12:51 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=402809514&ptid=24041982][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
可吾可以出埋個答案  我計到個數但係吾知岩吾岩



http://i.discuss.com.hk/d/images/r10/androidD.jpg [/quote]265



[url=http://m.discuss.com.hk][img=100,23]http://n2.hk/d/images/r10/mobile.jpg[/img][/url]

[7] 2014-11-19 08:04 PM

[quote]原帖由 [i]elvistsang420[/i] 於 2014-11-19 12:51 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=402809514&ptid=24041982][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
可吾可以出埋個答案  我計到個數但係吾知岩吾岩



http://i.discuss.com.hk/d/images/r10/androidD.jpg [/quote]265



[url=http://m.discuss.com.hk][img=100,23]http://n2.hk/d/images/r10/mobile.jpg[/img][/url]

eaglle 2014-11-22 09:28 AM

[font=標楷體]我先提供一個集合的公式: 用|A|代表A集合中的元素的數目, 例如, 若A={x,y,z}, 則|A|=3[/font]
[font=標楷體][/font]
[font=標楷體]公式: [/font]
(為了簡便起見, 以下我用AB或ABC代表  [img]http://latex.codecogs.com/gif.download?A\cap B, A\cap B\cap C[/img] 等等)

[img]http://sciencesoft.at/lpng/586c8fd7d3db844257a4137b149a7a912d37eca.png[/img]

[font=標楷體]這些公式的前兩個, 可以畫簡單的圓圈圖來解釋, 後面較複雜的, 就可以用類推來理解;

現在回到題目: 令A={第一信進入第一封的所有情況 (包括其它信的各種可能性)}, B, C...都同此
|A|=其它5信的各種情況 (第一信已固定在其封套中了)=5!=|B|=|C|=...
|AB|=第一,二信固定, 其餘各信的各種情況= 4!.....
...........

現在我們來算, 至少有一信進入它該進的封套, 就是[img]http://latex.codecogs.com/gif.download?A\cup B\cup C\cup D\cup E\cup F[/img][/font]

[img]http://latex.codecogs.com/gif.download?|A\cup B\cup C\cup D\cup E\cup F|=C^{6}_1 5!-C^{6}_2 4!+C^{6}_3 3!-C^{6}_4 2!+C^{5}_5 1!-C^{6}_6 0![/img]

[font=標楷體]其中出現C(6,2)等等, 是因為「兩兩交集」共有從6個集合中選出2個來做交集, 有那麼種可能, 而每種可能, 例如|AB|=4!

如果是要算「每信都不在它的封套中」, 那就只要用6!減去上面算出的數字即可[/font]

[[i] 本帖最後由 eaglle 於 2014-11-22 10:49 AM 編輯 [/i]]

eaglle 2014-11-22 10:45 AM

回覆 6# 的帖子

我在#7中打的公式, 就是用你所介紹的[url]http://sciencesoft.at/latex/[/url]的網頁, 否則無法在公式中夾中文,
再次感謝你分享, 真的很好用

[[i] 本帖最後由 eaglle 於 2014-11-22 10:46 AM 編輯 [/i]]

[7] 2014-11-22 12:23 PM

回覆 7# 的帖子

啊,這結構性解法proof我也很中意。硬爆對解數有時好煩,但對理解問題結構則是絕佳!
頁: [1]
查看完整版本: 組合