2011-01-22

離散幾題疑問(組合 圖論)

相關類題




我自己補上了座標
只考慮不經過(3,2)至(7,5)是不是太狹隘
是不是還要考慮(3,2)至(7,2) ,(3,2)至(7,3), (3,2)至(7,4)
(4,2)至(7,5)(7,4)(7,3)(7,2)等
(5,2)至(7,5)(7,4)(7,3)(7,2)等............
感覺算不完==
還是我根本想錯了


請助教指點了




~~~~~~~~~~~~~~~~~~~~~之前問的~~~~~~~~~~~~~~~~~~~~~
1.
只是想確定(b)用最小著色數就可以吧?

2. 3.
這兩題完全不懂==|
是第3章的範圍嗎

4.

ans:
每小時k個人 總共k*n人 所以 C(k*n,n) ,且有n個小時要排班(=相異箱子) ,
故n!*C(k*n,n)

不知是否正確


請助教跟各位達人指點一下了




8 則留言:

線代離散助教(wynne) 提到...

1. OK

2. (a) 題目希望你算出chessboard上所有不同的L型會有幾個, 這是屬於第三章的範圍沒錯
(b) 請你說明假設擲n次骰子, 甚麼時候的期望值會達到6n-4, 書上在談離散機率的那一節有提到相關的觀念

3. c(nk,k)是不夠的, 因為剩下的(n-1)個人沒有被分配, 所以應該是要k個k個一直選到最後才行, i.e.,
c(nk,k)c((n-1)k,k)...c(k,k) = (nk)!/k!^n

Lulu Hung 提到...
作者已經移除這則留言。
Lulu Hung 提到...
作者已經移除這則留言。
Lulu Hung 提到...

2.L型
我本以為是可以塞幾個 == = 害我想不出來

我參考習題3-113(a)作答的

所以L1=4 在 8格中可以有5種選擇
C(5,1)

所以L2=3 在 8格中可以有5種選擇
C(6,1)

且L型可以轉4個方向
所以總共個L型可能個數即4*C(5,1)*C(6,1)



3.骰子那題

列表觀察

丟n次時 ,總和 6n-4, 點數組合:

丟1次,總和2,點數組合:(2)

丟2次,總和8,點數組合:(2,6) (6,2)
(3,5) (5,3)(4,4)

丟3次,總和14,點數組合:
(2,6,6) (6,2,6) (6,6,2),
(3,5,6) (3,6,5)等6種
(4,4,6) (4,6,4) (6,4,4)

丟4次,總和20,點數組合:
(2,6,6,6) (6,2,6,6)等4種
(3,5,6,6) (6,3,5,6)等12種
(4,4,6,6) (4,6,4,6)等6種

丟5次,總和26,點數組合:(2,6,6,6,6)
(3,5,6,6,6)
(4,4,6,6,6)等
....

觀察表格可知,總和為6n-4時,在n>=2時,其點數組合必為(2,6),(3,5),(4,4)加上n-2個6的組合

且丟出1 ,2, 3, 4, 5, 6點之機率分別為0.2,0.2,0.2,0.2,0.2.,01,0.1
故方程式為 (2,6加n-2個6)+ (3,5加n-2個6)+ (4,4加n-2個6)
C(n,1)* C(n-1,1)*C(n-2,n-2)0.2*0.1*(0.1)^(n-2) + C(n,1)* C(n-1,1)*C(n-2,n-2)0.2*0.1*(0.1)^(n-2) + C(n,2) *C(n-2,n-2)*(0.2)^2*(0.1)^(n-2)
,n>1

請問是這樣麼?
且答案需要化簡嗎,感覺很亂(課本上許多題目也沒化簡 令我頗感疑惑)

線代離散助教(wynne) 提到...

2. L型: OK

3.骰子那題: Don't worry, since it has stated that you only need to write down the formula and explain the cases

Lulu Hung 提到...

謝謝助教唷
我又在文章最前面
補上了一題相關類題
請幫忙看看

線代離散助教(wynne) 提到...

From (0,0) to (3,5) to (9,7): c(8,3)*c(8,6)

From (0,0) to (2,6) to (9,7): c(8,2)*c(8,7)

From (0,0) to (1,7) to (9,7): c(8,1)*c(8,8)

From (0,0) to (7,2) to (9,7): c(9,7)*c(7,2)

From (0,0) to (8,1) to (9,7): c(9,8)*c(7,1)

From (0,0) to (9,0) to (9,7): c(9,9)*c(7,0)

Sum up all the above, then you will get the answer

Lulu Hung 提到...

謝謝助教的回覆 我暸解了:D