Processing math: 59%

考試

103成大資聯離散[參考解答]

1. (20%) Don’t just write down the answer without explanations.

(a) Determine the number of paths in the xy-plane from (m,n) to (p,q), m,n,p,q positive integer or zero, m<p,n<q, where each such path is made up of individual steps going one unit to the right (x,y)(x+1,y) or one unit upward (x,y)(x,y+1).
(b) If (m,n)=(0,0),(p,q)=(7,4), how many of the paths in part (a) do not use the path from (2,2) to (3,2) to (4,2) to (4,3)?
(c) If (m,n)=(0,0),(p,q)=(7,4), how many of the paths in part (a) do not pass through the points (0,1),(1,2),(2,3),(3,4)?
(d) If an additional type of move (x,y)(x+1,y+1) is allowed, how many of the paths in part (a) if (m,n)=(0,0),(p,q)=(7,4)?

參考解答:
(a) (pm)+(qn)(pm)!(qn)!
(b) \binom{11}{7} – \binom{4}{2} \binom{4}{1}
(c) \binom{11}{7} – \binom{11}{3}
(d) \binom{11}{7} + \dfrac{10!}{6!3!} + \dfrac{9!}{5!2!2!} + \dfrac{8!}{4!1!3!} + \dfrac{7!}{3!4!}


2. (20%) Don’t just write down the answer without explanations.

(a) If the cost of each edge is given, determine the cost of the minimum spanning tree in the following figure?

圖片請看原檔

(b) How many different spanning trees in the following figure?

圖片請看原檔

(c) How many different spanning trees in the following figure?

圖片請看原檔

參考解答:(a) 29 (b) 40 (c) 4 \times 40^4


3. (10%) Find a formula for the convolution of each of the following pairs of sequences where n belongs to integers.

(a) a_n = 1, \, 0 \leq n \leq 5, \, a_n = 0, \, \forall n \geq 6; \\ b_n = n, \, \forall n \geq 1.
(b) a_n = (-1)^n, \, b_n = (-1)^n, \, \forall n \geq 1.

參考解答:
(a)
c_n = 6n – 15, \, \forall n \geq 6. \\ c_0 = 0, \, c_1 = 1, \, c_2 = 2, \, c_3 = 6, \, c_4 = 10, \, c_5 = 15.
(b)
c_0 = c_1 = 0, \, c_n = (n-1)(-1)^n, \, \forall n \geq 2.


試題(pdf):連結

有任何問題,或想要完整解釋的,歡迎在下方留言唷!

7 留言

  1. leo

    不好意思
    想請問2(b)的40是怎麼算的

  2. tinge

    請問一下最後一題的a跟b是怎麼算的

  3. tinge

    (答案是不是反了)

發佈留言