※ [本文轉錄自 NTU-Exam 看板 #1FgtP2fG ]
作者: peter506g (一氧化二氫) 看板: NTU-Exam
標題: [試題] 100下 呂育道 離散數學 第二次期中考
時間: Thu May 10 16:03:12 2012
課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰呂育道
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰101/5/10
考試時限（分鐘）：180
是否需發放獎勵金：
（如未明確表示，則不予發放）
是
試題 :
Problem 1 (10 points) Let A be a finite set. Prove that there is a one-to-one
correspondence between the set of equivalence relations on A and its set of
partitions.
Problem 2 (10 points) Let A1∪A2∪A3, where A1 = {1,2}, A2 = {2,3,4}, and
A3 = {5}. Define relation R on A so that xRy if x and y are in the same Ai
for at least one i. Is R an equivalence relation?
tr
Problem 3 (10 points) How many 6 ×6 (0,1)-matrices A are there with A = A ?
tr
(Recall that the ith row of A is defined to be the ith column of A.)
Problem 4 (10 points) A room has 800 chairs. How many chairs must be occupied
to guarantee that at least two people have the same first and last initials of
name? (If a person is called David Letterman, the first initial is "D" and the
last initial is "L".)
n
Problem 5 (10 points) Derive ψ(p ), when p is a prime and n ≧ 1
Problem 6 (10 points) In how many ways can we arrange the integers 1,2,3,...,8
on a line so that there are no occurences of the patterns 12,23,...,81? For
example, 87654321 is valid, but 12345678 is not. (A formula suffices. No need
to evaluate the answer to an integer.)
Problem 7 (10 points) In how many ways can the integers 1,2,3,...,10 be
arranged that no even integer i is in the ith position? (A formula suffices. No
need to evaluate the answer to an integer.)
Problem 8 (10 points) What is the number of integer solutions to
x1 + 2*x2 + 3*x3 + ... + 5*x5 = 5
where xi ≧ 0, i = 1,2,3,4,5?
# +
Problem 9 (10 points) Let q (m,n) denote the number partitions of m∈Z into
n distinct positive summands. Let q(m,n) denote the number of partitions of m
# n
into exactly n positive summands. Prove that q (m,n) = q(m - ( ), n).
2
Problem 10 (10 points) In how many ways can three x's, three y's, and three
z's be arranged so that no consecutive triple of the same letter appears? For
example, xxyxyzyzz and yyxxzzyxz are valid. (A formula suffices. No need to
evaluate the answer to an integer.)
+
P.S. 第九題的第一行裡面的 m E Z 那個E是"屬於"符號 (我找不到...
P.S. 呃已修正∈ 感謝下方推文支援(不過那一排冒號是怎麼回事...