1
$\begingroup$

I got two varieties for the same question:

  1. Ways that four books out of a bag of 12 books can be placed on a shelf.
  2. 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.

Question:

Am I correct in reasoning for the above solutions and creating the correct mental models?

Ref: http://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_2.pdf

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?

$\endgroup$
  • $\begingroup$ Personally, I view the difference in the questions this way. In the first problem, we select four of the twelve books in the bag, then arrange them on the shelf in some order: $$\binom{12}{4} \cdot 4! = \frac{12!}{4!8!} \cdot 4! = \frac{12!}{8!} = 12 \cdot 11 \cdot 10 \cdot 9$$ In the second problem, we select four of twelve books on the shelf to place in the bag. $$\binom{12}{4} = \frac{12!}{4!8!} = \frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8!}{4 \cdot 3 \cdot 2 \cdot 1 \cdot 8!} = \frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1}$$ $\endgroup$ – N. F. Taussig May 20 '16 at 9:16
1
$\begingroup$

Let's simplify this to choosing $2$ books from $3$

  • Putting them on a shelf, if the books in the bag are $\{A,B,C\}$ then the possibilities are:
    • $(A,B)$
    • $(A,C)$
    • $(B,C)$
    • $(B,A)$
    • $(C,A)$
    • $(C,B)$
  • Putting them in a bag, if the books on the shelf are $(A,B,C)$ then the possibilities are:
    • $\{A,B\}$
    • $\{B,C\}$
    • $\{C,A\}$

Each two-element set corresponds to $2 \times 1=2$ two-element ordered sets, since order matters in an ordered set, so while you have $3 \times 2 = 6$ possibilities putting on a shelf, you instead have $\dfrac{3 \times 2}{2 \times 1}=3$ possibilities putting in a bag

In terms of your post-scriptum, you might look at comparing

A    1  1  -  2  2  - 
B    2  -  1  1  -  2 
C    -  2  2  -  1  1

with

A    X  X  - 
B    X  -  X 
C    -  X  X
$\endgroup$
  • $\begingroup$ Sorry, I may sound stupid but I am a beginner so still trying out hard to fit peaces together and getting analogies correct. What I inferred from the question and couple of answers is when say putting objects in a bag we mean something like a closed bag and not some open box like structure hence we can't actually see inside it once we put an object inside it. Hence order doesn't matter there, on the other hand putting books on shelf means we can actually see the objects and hence order matters for us. $\endgroup$ – CodeYogi May 20 '16 at 10:51
  • $\begingroup$ Second important observation is number of ordered outcomes are greater than the unordered one, right? $\endgroup$ – CodeYogi May 20 '16 at 10:53
  • $\begingroup$ Yes. The number of ways of ordering a set is the factorial of the number of elements of the set. So if there are at least two elements of the selected set then there will be more ordered outcomes. If instead you regard different orderings of the same selected set as equivalent (and so only counted once) then there will fewer unordered outcomes $\endgroup$ – Henry May 22 '16 at 16:34
0
$\begingroup$

For the first question, I think you are correct. I can't be sure because the second paragraph is a little confusing, but to make things clear, each leaf in the tree you build is a possible arrangement of books on the shelf. For example, a few leaves might be $(4, 2, 7, 10)$, $(1, 2, 3, 4)$, and $(4, 3, 2, 1)$. Note that the last two are counted separately because the order matters.

For the second question, first we build the same tree as above. However, since we are just putting the books into a bag, it doesn't matter whether the order is $(1, 2, 3, 4)$ or $(4, 3, 2, 1)$: the same books are going in. Thus we have to remove 'duplicate' leaves, i.e. leaves which contain the same books but in different orders. For any set of books -- say $(a, b, c, d)$ where all books are distinct -- there are $4 \cdot 3 \cdot 2 \cdot 1 = 24$ ways to organize them by the previous reasoning. So each leaf in the original tree with $12 \cdot 11 \cdot 10 \cdot 9$ leaves is counted $4 \cdot 3 \cdot 2 \cdot 1$ times, meaning that the number of non-duplicate leaves is $$\frac{12 \cdot 11 \cdot 10 \cdot 9}{4 \cdot 3 \cdot 2 \cdot 1}$$

(Re. your PS: I'm not sure the 'bit-counting' method is very useful here, but the second question is equivalent to counting the number of 12-bit binary numbers with 4 '1's.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.