※ [本文转录自 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)