I got two varieties for the same question:
- Ways that four books out of a bag of 12 books can be placed on a shelf.
- Ways to choose 4 books out of 12 arranged on a shelf and put them in a bag.
Answer for the first one is $12 * 11 * 10 * 9$ but for the second one the answer is $(12 * 11 * 10 * 9) / (4 * 3 * 2 * 1)$ since we don't care about the order.
I am satisfied with the first solution but the solution for the second question opens a door for confusions for me. If I understand correctly in the first question it is assumed that order is important and in the second case it is not. Anyways I will try to think backwards.
My thought process for the first questions is:
There are sequence of choices made after another with the remaining choice decreasing in each step (I mentally see it as a tree). So, for the first book I have 12 choices, next for the second level of the tree I have 11 choices and so on, since we need four choices we would go 4 levels deep. The total number of leaves would give us the required solution which is $12 * 11 * 10 * 9$.
Lets, investigate more. The leaves represents total number of choices and if we see as a tree then each leaf would contain the nodes from all the ancestors but in different orders hence there would be repetition for eg: (1, 2, 3, 4), (1, 3, 2, 4) and so on, now it depends on the question if it needs to consider theses leaves equal or different (ordered I think?).
For the second question:
Lets apply the same thought process again. The reasoning seems to work fine till first half of my thought process discussed above in the first half. But the solution divides the choices by some series of multiplication so, basically the author has reduced the number of available choices hence it must have removed some duplicates, the only duplicates(equivalence classes as told in the source) I see here are the repeated tree leaves if I see them as a set hence it means we don't need duplication here.
Am I correct in reasoning for the above solutions and creating the correct mental models?
PS: This might be unrelated but seems important to me.
In some places people try to solve some problems by reducing the problem to a sequence of bits and choosing all the possible number of places for 1's, how to apply and understand this rule?