Question 1. (9 marks) Let n 1 be a positive integer and let [n] denote the...

Transcribed Image Text:

Question 1. (9 marks) Let n 1 be a positive integer and let [n] denote the set {1, 2, . . ., n}. (a) (3 marks) Let S = {(A, B): A, B C [n], |ANB| = 1}. By counting S in two ways, prove that n3n-1 (%) k=1 k2n-k (b) (3 marks) Let Tn that = {(x,X,Y) : X,Y C [n], x X, Y CX \ {x}}. By counting T in two ways, prove n n3n-1 = (1) n k2k-1 k=1 (c) (2 marks) Construct a bijection between Sn and Tn and state its inverse. Question 1. (9 marks) Let n 1 be a positive integer and let [n] denote the set {1, 2, . . ., n}. (a) (3 marks) Let S = {(A, B): A, B C [n], |ANB| = 1}. By counting S in two ways, prove that n3n-1 (%) k=1 k2n-k (b) (3 marks) Let Tn that = {(x,X,Y) : X,Y C [n], x X, Y CX \ {x}}. By counting T in two ways, prove n n3n-1 = (1) n k2k-1 k=1 (c) (2 marks) Construct a bijection between Sn and Tn and state its inverse.