Math340 Discrete Structure Midterm Exam
Name: Mc D:
• Do not turn this page over until we tell you that the exam starts! You have two hours from that point to complete the exam.
• The exam counts 5 questions worth 20 marks each, adding-up to 100 marks.
Copyright By PowCoder代写 加微信 powcoder
• This is a closed book examination. But you may use the table of power series below.
• Calculators are allowed, given that you can’t write notes in them. Smarter devices are obviously forbidden.
• Answer all problems in the booklet provided with this exam. Show all your work.
• Please return this exam with the booklet in the end.
• Good luck!
Winter 2020
1−x =1+x+x2 +…+xN
1−x= xn n=0
1 ∞ n + r − 1 n
√ ∞ 2n (−1)n+1
n 4n(2n−1)xn
e x = ∞ x n n=0 n!
ex+e−x ∞ x2n
cosh(x) = 2 =
ex − e−x ∞ x2n+1 sinh(x) = 2 = (2n + 1)!
Question 1
How many integers 1 ≤ n ≤ 1000 are neither perfect squares, perfect cubes, nor multiples of 7?
Question 2
(a) Find an algebraic proof the following identity.
n−1 n n n2 = kk
(b) Find a combinatorial proof of the same identity.
Question 3
Use the Generating Functions Method to solve the recurrence an = 3an−1 + 4n with initial condition a0 = 1.
Question 4
Use an Exponential Generating Function to count the number of strings of length n over the alphabet {0, 1, 2} with an even number of `0′ and an odd number of `1′.
Question 5
A function f : {0,1…n} → {0,1…n} is called nilpotent if for all x ∈ {0,1…n}, there is a number k0 such that for all k ≥ k0, fk(x) = 0. Here fk denotes the k-th iterate: f k = f ◦ f ◦ · · · ◦ f (k times).
(a) Show that the function f dened by the following table is nilpotent. x 012345
f(x) 0 4 0 4 2 2
(b) Show that if f : {0,1…n} → {0,1…n} is nilpotent, then we can simply take
k0 =ninthedenition,i.e. showthatforallxandforallk≥n,fk(x)=0. Hint: One of the key steps here might be the Pigeonhole Principle…
(c) Apply Joyal’s bijection to the function in part (a) and draw the corresponding vertebrate.
(d) Generalizethisexampletoshowthatthenumberofnilpotentfunctionson{0,1…n} is (n + 1)(n−1).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com