Let S be a finite set of size n. Determine (in terms of n) the number of pairs o
ID: 3119073 • Letter: L
Question
Let S be a finite set of size n. Determine (in terms of n) the number of pairs of sets (A, B) where both A and B are subsets of S, and where no element of S is both in A and B. Prove the formula you find. So, for example, if S has one element called s, then the options for (A. B) are: (phi, phi), (phi, {s}) and ({s}, theta). Let S be a finite set of size n as in the previous exercise. We consider all pairs of sets C D where D S. Show that the number of such pairs is the same as the numbers of pairs (A, B) from the previous exercise.Explanation / Answer
I am solving the question 1.16, please post one more question to get the answer to the problem 1.17
1.16 There will be three cases possible for each element in the set
Case 1: Element doesn't belong to any set
The element may be s doesn't belong to neither A nor B
Case 2: Element belongs to A and not to B
The element will belong to A but not to B
Case 3: Element belongs to B but not to A
The element will belong to B but not to A
Number of cases will be 3^n(for each element there ar e three choices, hence total will be 3^n)
1.17 There will be three cases possible for each element in the set
Case 1: Element doesn't belong to any set
The element may be s doesn't belong to neither C nor D
Case 2: Element belongs to D and not to C
The element will belong to D but not to C
Case 3: Element belongs to both D and C
The element will belong to both D and C
Number of cases will be 3^n(for each element there ar e three choices, hence total will be 3^n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.