After reading the Slog handout, I created my blog in Blogger on September. But I almost forgot to write the post on it. Unhappily, this is just my first slog for csc236. So I will just summarize what I did last month.
Going back to the second lecture, I was confused and got a trouble to understand the system of "partition" and "bijection".
|| P(n): Every set with n elements has exactly 2^n subsets
||
|| Scratch work: P(0): {} → {{}}
|| P(1): {y} → {{}, {y}
|| P(2): {y, x} → {{}, {y}
|| ---↓---↓----------------partition to count
|| {x}, {y, x}}
Because I didn't get why we do the partition to count number of subsets, I asked Danny Heap after class.
After he explained again, I get it. For example, the number of subset of size 3 (I'll call it a 3-subset) is the same as the number of 2-subsets + 3-subsets in the previous step ('step' means each cases like P(0), P(1), P(2)...). Because 2-subsets in the previous step become 3-subsets in the next step just by adding up a new element.
Understanding of "partition" and "bijection" helped me to solve #3 question from our Assignment1 because it asks us to find a formula for the number of 3-subsets by using formula for the number of 2-subsets.
