※ [本文轉錄自 NTU-Exam 看板 #1JHII6fL ] 作者: aalexx (aalexx.S) 看板: NTU-Exam 標題: [試題] 102下 呂育道離散數學 第一次期中 時間: Wed Apr 9 18:44:17 2014 課程名稱︰離散數學 課程性質︰資工系選修 課程教師︰呂育道 開課學院：電機資訊學院 開課系所︰資工系 考試日期（年月日）︰March 27, 2014 考試時限（分鐘）：180 是否需發放獎勵金： （如未明確表示，則不予發放） 試題 : 注: (n,2) 表C n取2 Note: Ypu may use any results proved in the class unless stated otherwise. P1.(5 points) Calculate 4!/2! P2. Consider the expansion of (x+y+z+w)^5. (1) (5 points) Determine the coefficient of x^2yz^2. (2) (5 points) Determine the sum of all coefficient. P3.(5 points) Let n be any positive integer. Show that (n,0)+(n,2)+(n,4)+...=(n,1)+(n,3)+... P4.(10 points) Recall the Catalan number bn = (2n,n)-(2n,n-1) for n>=1. It is equal to, for example, the number of binomial random walks which start at the origin and end at the origin in 2n steps without being in the negative territory. (1)Show that (2n,n)-(2n,n-1) = (2n,n)/(n+1). (2)Consider 2 types of moves R: (x,y)->(x+1,y) and U:(x,y)->(x,y+1). How many ways can one go from (0,0) to (6,6) without ever crossing the line y=x in 12 moves using only R and U moves? P5.(10 points) Let X=(p->q)^(q->r)->(p->r) be a boolean expression. Please derive the simplest logically equivalent expression. P6.(10 points) Let A, B, C be any sets. Prove or disprove following statement: If if A 屬於 B and B 不屬於 C, then A 不屬於 C. P7.(10 points) Let A,B be two sets with |A∩B| = 3, and |A∪B| = 8. (1) How many C satisfy A∩B 屬於 C 屬於 A∪B. (2) How many C satisfing (1) contain an even number of elements? P8.(10 points) Show that Σ[i=1 to n] (i2^i) = 2+(n-1)2^(n-1) by induction. P9.(10 points) Let n be nonegative onteger. Show that (2n,n) = Σ[k=0 to n](n,k)^2. P10.(20 points) There are two candidates A and B in an election. Let A receive a votes and B receive b votes, a>b, before the votes are revealed one by one and counted. On the vote-counting process, a total of a+b votes will be announced sequentially such as "A A B B A A B ...". Call a vote announcing sequence legal if A's accumulated vote count is greater than B's throughout the vote-counting process. For examplem, the above sequence is not legal because after the 4th vote announced, A's and B's votes break even. (1) What is the toal number of possible vote announcing sequences (here, legality is not a concern)? (2) Show that the number of illegal sequence is (a+b-1,a) given that the first announced vote is for B. (Hint: there must be a tie and recall the reflection principle.) (3) Show that the number of illegal sequences is (a+b-1,a) given that the first announced vote is for A.(Hint: there must be a tie and recall the reflection principle.) (4) Finally, show that the total number of legal sequence is (a-b/a+b)(a+b,a) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.115.66.210 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1397040262.A.A55.html ※ 編輯: aalexx (58.115.66.210), 04/09/2014 18:45:05

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: w4a2y4 (140.112.4.192), 03/14/2016 19:28:25