Discrete Mathematics
2nd midterm exam, spring 2022
Note: You have to show/explain how you derive the answers.
1. (16 points) Let n ∈ N. Find a closed form for each of the following summations:
Copyright By PowCoder代写 加微信 powcoder
{1,2,…,n} and Y = {0,1} are there such that • f is an injection (1-1 function)?
• f is a surjection (onto function)?
3. (10 points) How many ways are there for a horse race with four horses
to finish if ties are possible?
4. (12 points) For each of the following statements, determine whether it is true or false. (Note: ∅ is the empty set.)
(a.) ∅∈∅ (b.) {∅}∈{∅} (c.) {∅}⊆{∅}
(d.) ∅⊆∅ (e.) ∅∈{∅} (f.) ∅⊆{∅}
5. (15 points) What is the 5934th 3-permutation of {x ∈ N: 1 ≤ x ≤ 20} in lexicographic order? (The 1st is the smallest one, namely (1, 2, 3).)
2. (10 points) Let n ∈ N. How many functions f: X → Y with X =
6. (10 points) Let A be a countable set and B be an uncountable set. Show that B − A is uncountable.
7. (15 points) Let S be the set of infinite sequences, where each sequence consists of integers ranging from 0 to 9. Show that S is uncountable.
8. (15 points) Solve the following recurrence
0, if n = 0
T(n)= 0, ifn=1 T(n−1)+T(n−2)+2n, foralln≥2.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com