Online Course Discussion Forum
Example Problems Question
Hello! For Class 7 of MC II-A Comb, I did some problems as extra practice and checked my answers.
For Problem 7.2 Part (b), it should be a_n=2a_(n-1)+1 because it is A_n=2^n-1. This is because each of the n friends can "say" "yes" or "no" to being invited. But at least one has to come, so minus 1, which is the case where no friends are invited. How is it a_(n+1)=2a_n+2? Even for the second term, it doesn't work, for a_1, it is 1, but a_2 is supposed to be 3: person 1 only goes, person 2 only goes, and both person 1 and person 2 go.
For Problem 7.4 (b) and (c), for b, how can we assume set A is fixed? Also, a set does not matter the order of its elements, unless I remembered wrong (:D) for (c), why is the solution a bijection? I don't completely understand.
Thank you so much
Thanks again!
Starting with 7.2(b), be careful with the wording "at least one friend but not all the friends". You're correct we need to have 2^n total options, minus one because we need at least one friend (all friends cannot say "no"), but we have another minus one because we can't invite all the friends (all friends cannot say "yes").
This gives $a_n = 2^n - 2$ or recursively $a_{n+1} = 2\cdot a_n + 2$. It can be good to review 7.6 from here as well, as that question is similar.
For 7.4, let's start with (c) for an example of a bijection. Remember a bijection is a perfect matching of one set with another set. More formally, we can think of this as a function (with input and output) between the two sets.
The bijection from subsets of {1, 2, 3, 4, 5} of size two to two numbers chosen (repeats allowed) from {1, 2, 3, 4}:
$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c} \text{input} & \{1, 2\} & \{1, 3\} & \{1, 4\} & \{1, 5\} & \{2, 3\} & \{2, 4\} & \{2, 5\} & \{3, 4\} & \{3, 5\} & \{4, 5\} \\ \hline \text{output} & \{1, 1\} & \{1, 2\} & \{1, 3\} & \{1, 4\} & \{2, 2\} & \{2, 3\} & \{2, 4\} & \{3, 3\} & \{3, 4\} & \{4, 4\} \end{array}$$
Note every input (subsets of size 2) matches with one output (two numbers chosen with repeats...) and all the inputs and outputs are covered. This is what a bijection is.
Here we organized the bijection in a nice way, where we could give a "formula" that maps a subset {a, b} to the two numbers {a, b-1}. However, actually any ordering we put for the 10 outputs would still be a bijection. Note since there are 10 outputs, there would be 10! total bijections. This is the idea from part (b). All that really matters is that we have 10 inputs and 10 outputs.
Hope this helps a bit!
社交网络