※ [本文转录自 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. 呃已修正∈ 感谢下方推文支援(不过那一排冒号是怎么回事...