課程名稱︰離散數學
課程性質︰系內選修
課程教師︰呂育道
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2014/03/27
考試時限（分鐘）：180 mins
試題 :
1. (5 pts) Calculate 4!/2!.
5
2. (10 pts) Consider the expansion of (x+y+z+w) .
2 2
1) (5 pts) Determine the coefficient of x yz .
2) (5 pts) Determine the sum of all the coefficients.
3. (5 pts) Let n be any positive integer. Show that
C(n,0) + C(n,2) + C(n,4) + ... = C(n,1) + C(n,3) + C(n,5) + ...
4. (10 pts) Recall the Catalan number b = C(2n,n) - C(2n, n-1) for
n
n ≧ 1. It is equal to, for exameple, 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) (5 pts) Show that C(2n,n) - C(2n,n-1) = C(2n,n)/(n+1)
2) (5 pts) Consider 2 types of moves R: (x,y) → (x+1,y) and
U: (x,y) → (x,y+1). How many ways can on go from (0,0) to (6,6)
without ever crossing the line y=x in 6 moves using only R and U
moves?
5. (10 pts) Let Φ = (p→q) or (q→r) → (p→r) be a Boolean expression.
Please derive the simplest logically equivalent expression.
6. (10 pts) Let A, B, C be any sets. Prove or disprove following statement:
If A⊆b and NOT(B⊆C), then NOT(A⊆C).
7. (10 pts) Let A, B be two sets with |A∩B| = 3, and |A∪B| = 8.
1) (5 pts) How many C satisfy A∩B ⊆ C ⊆ A∪B ?
2) (5 pts) How many C satisfying 1) contain an even number of elements?
n i n+1
8. (10 pts) Show that Σ i2 = 2 + (n-1)2 by induction.
i=1
n 2
9. (10 pts) Let n be a nonnegative integer. Show that C(2n,n) = Σ C(n,k) .
k=0
10. (20 pts) 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 context. In 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 example, the above sequence
is not legal because after the 4th vote is announced, A's and B's votes
break even.
1) (5 pts) What is the total number of possible vote announcing sequences
(here, legality is not a concern)?
2) (5 pts) Show that the number of illegal sequence is C(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) (5 pts) Show that the number of illegal sequence is C(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) (5 pts) Finally, show that the total number of legal sequences is
C(a+b,a)(a-b)/(a+b).