I'm trying to understand the question 4 in Stanford HW solution. For part a, I don't understand why the answer is $$ comb(10,8) 2^8 $$ I think of the problem as the following:
- By how many ways can we choose those 10 shoes (since there are no pairs can appear, the only option we have is to choose a single shoes from each pair)?
- By how many ways can we choose the 8 from those 10?
The answer for 2 is simply $$ comb(10,8)$$ but the answer for 1 is $$2^{10}$$ However, in the solution it's told that the answer is $$2^8$$ Which I don't get it, I feel I'm missing something in my way of thinking in this problem. Any hint is appreciated.
The book is conceptualizing it as choose $8$ of ten pairs to contribute a shoe; and then choose one shoe from each of the eight pairs.
Your solution over-counts by a factor of $4$ because for the two unused shoes of the $10$ you chose, you could change the footed-ness of either or both of the shoes from their pairs. [That is, unused pair A: choose left or right; unused pair B: choose left or right.]