Compsci 120  Assignment 2

1.（字符串，集合）
（a）列出集合{{∅}，∅，{∅}，∅}的所有不同子集。
（b）假设A，B和C是集合，并且A∩B = A∩C和A∪B = A∪C。证明
B = C
（c）令j =“ java”，r =“ ruby​​”和p =“ python”为字符串。考虑字符串R =
jr，S = rp，T = jp。

ii。列出p的所有子串。
iii。令| i |表示字符串i的后缀数。 | R | + | S | + | T |是

2.（关于计数的谎言）
（a）关于计数问题的索赔，以及与此索赔相对应的“证明”，

26
3
</ s> </ s> </ s>
·

49
2
</ s> </ s> </ s>
525

1逻辑错误是推理中的错误，而不是结论。也就是说：如果您想解释为什么有人

outcomes所有结果的数量是通过有序重复的有序选择来计算的

“任务“在5张纸牌中准确获得3张3张黑卡”可以分为

26
3
</ s> </ s> </ s>

49
2
</ s> </ s> </ s>

26
3
</ s> </ s> </ s>
·

49
2
</ s> </ s> </ s>

26
3
</ s> </ s> </ s>
·

49
2
</ s> </ s> </ s>
525
（b）从（a）中找到索赔的实际可能性
3.（计数）

(a) Suppose that Professor Albus Brian Dumbeldore was moving to Hogwarts, and wants to
ask the NZ Post office to redirect mail to him.
 Prof. Dumbeldore has three possible titles (Headmaster, Prof., Professor) that can
go in the front of his name. Any one of these titles can be listed, or no title can be
listed.
 His name can then be listed in any of the formats “First Middle Last”, “Last, First
Middle”, “First Last”, “Last, First”, or just “Last”. Each time a name is used, it
can either be written out in full (“Brian”) or just given by a first initial (“B”).
 Finally, suppose that he has four possible honorifics (O.M, X.J(sorc), Grand Sorc,
D.Wiz), that can go on the end of his name. Any subset of these can go on to the
end of his name, and the order matters here (i.e. listing them in a different order
technically yields a different “name.”)
 Any possible combination of title-name-honorifics is valid.
How many title-name-honorific combinations would he need to list with the New Zealand
Post Office, to ensure that mail sent to any of these names would go to him?
(b) Suppose that the order in which the honorifics is listed does not matter. How does this
(c) What is the probability that the letter is addressed as “Professor Albus B Dumbeldore”
or “Prof. Albus Brian Dumbeldore”, assuming that the order in which the honorifics is
listed does not matter, and all combinations of title-name-honorifics occurs with equal
probability? Justify
4. (Functions)
(a) Let X = {1, 2, 3, 4}. State with reason which of the rules defined below is (or is not) a
function with domain and codomain both equal to X.
i. f(2) = 3, f(1) = 4, f(2) = 1, f(3) = 4,f(4) = 1,
ii. g(3) = 1, g(4) = 3, g(1) = 2,
iii. h(2) = 1, h(3) = 4, h(1) = 2, h(2) = 1, h(4) = 3
(b) i. Define f : R → R by the rule f(x) = 2x
4 + 4x
2 + 1 for every real number x. Let
g : {∗, +, %, ×} → R be a function defined by the rule: g(∗) = 1, g(+) = 2, g(%) =
−1, g(×) = −2. Find the domain and range of f ◦ g.
ii. Let f : R → R and g : R
≥2 → R be functions defined as follows2
:
f(x) = √
x and g(x) = p
(x − 2)
Does g ◦ f exist? Justify
(c) Define a function f : {1, 2, 3, 4, 5, 6} → {1, 2, 3, 4, 5, 6} by the rule f(1) = 3, f(2) =
4, f(3) = 6, f(4) = 2, f(5) = 5, f(6) = 1.
For any positive natural number n, let f
n
(x) = f ◦ f ◦ f ◦ . . . ◦ f
| {z }
n times
(x). Calculate f
1000(x)
and f
1001(x) for every x in {1, 2, 3, 4, 5, 6}. Justify your answer
2R
≥2 denotes all real numbers greater than or equal to 2
3