Online Course Discussion Forum
Example Problems Question
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!
Social networks