1
$\begingroup$

In this question, I tried to get at some underlying confusion I'm experiencing when it comes to the multiplication principle and order: right now it seems to me that sometimes multiplying expressions account for order, and sometimes they do not.

The original problem essentially had 6 distinct choices from group $A$ and 5 distinct choices from group $A'$, and asked for the number of distinct groups of 4 objects that had exactly 2 members from $A$. It was established that the correct reasoning was:

$$ \Big( \underbrace{{~ \color{blue}{6} ~}}_{A_1} \cdot % \underbrace{{~\color{blue}{5} ~}}_{A_2} \Big) % \cdot % \tfrac{1}{2!} % % \; \cdot \; % % \Big( \underbrace{{~ \color{green}{5} ~}}_{A_1'} \cdot % \underbrace{{~ \color{green}{4} ~}}_{A_2'} \Big) % \cdot % \tfrac{1}{2!} $$

which corresponds to the expression in terms of combinations:

$$ _6C_2 \; \cdot \; _5C_2 $$

What is bothering me is that, in the first case, the multiplications $\color{blue}{6 \cdot 5}$ and $\color{green}{5 \cdot 4}$ apparently account for order (hence division by $2!$, for each), whereas in the second case the multiplication of $_6C_2$ and $_5C_2$ does not account for the number of ways 2 objects are ordered. How come? Is it simply because we have already "taken the ordering" out of combinations and so multiplying them doesn't account for order?

To further clarify, what if I want to make a group from three sets, where $A$ has 8 elements, $\color{orange}{B}$ $\color{orange}{\text{has 6 elements}}$ and $\color{purple}{C}$ $\color{purple}{\text{has $12$ elements}}$, and I want to have 3 elements from $A$, $\color{orange}{\text{4 elements from $B$}}$ and $\color{purple}{\text{5 elements from $C$}}$. Following the above, it seems the answer would just be: $$ \boldsymbol{_8C_3} \; \cdot \; \color{orange}{_6C_4} \; \cdot \; \color{purple}{_{12}C_5} $$

But when I look at that, what I see is a sequence of decisions, where we're multiplying the number of possibilities at each step, which leads me to think that it is a permutation, so I really want to "divide out the number of ways of permuting three objects," i.e. I'm tempted to write:

$$ \big( \boldsymbol{_8C_3} \; \cdot \; \color{orange}{_6C_4} \; \cdot \; \color{purple}{_{12}C_5} \big) \cdot \tfrac{1}{3!}, $$

which I believe is actually wrong. Can anyone provide a systematic way of knowing $\color{red}{\text{when multiplying options accounts for ordering, and when it does not?}}$

$\endgroup$
1
$\begingroup$

Think of the multiplication principle as counting the number of ways there are to make a particular sequence $C_1, C_2, C_3,\dots$ of choices for an $s$-stage decision process so that $C_0,C_1,\cdots C_s$ produces one of the outcomes you want to count. If there are $n_i$ ways in which you can make the specific choice $C_i$, where $n_i$ is independent of the particular choices made before the $i$-th stage, the number of ways to make the entire sequence of choices will be $\prod n_i$. If your multi-stage process generates each thing you want to count exactly once, the number of things you wanted to count is $\prod n_i$. However, sometimes, it’s easiest to come up with a multi-stage process (perhaps depending on order) that generates each thing you want to count multiple times, in which case you can (if the multiple is a constant) correct your answer by division.

In your example of choosing from sets $A$, $B$, and $C$, you set up your stages so that you always chose from set $A$ first, then $B$, then $C$. So you did not generate results from each ordering of $A$, $B$, and $C$, which is what you are wondering whether you should divide by.

In fact, it would have been hard to use the multiplication principle if your stages were

  1. Choose one of the three sets to choose elements from.
  2. Choose the required number of elements from that set.
  3. Choose another of the three sets.
  4. Choose the required number of elements from that set.
  5. Choose the required number of elements from the remaining set.

because, while you would produce every outcome six times, the number of choices at some stages would depend on the particular choices made at other stages.

$\endgroup$
  • $\begingroup$ Thank you. I'm still struggling with it though because of the sentence "you always chose from set $A$ first, then $B$, then $C$" -- so doesn't this assume an order, which I don't want to do? I can see why that means I haven't already accounted for all possible orders of $A$, $B$ and $C$, but I don't feel I'm "getting it" enough to recognize it systematically... $\endgroup$ – Rax Adaam Nov 21 '18 at 23:31
  • $\begingroup$ The more I think about it, the more it seems to me "where $n_i$ is independent of the particular choices made before the $i$-th stage" seems to be at the heart of it, but I don't know how. $\endgroup$ – Rax Adaam Nov 22 '18 at 0:17
  • 1
    $\begingroup$ What I think is key to focus on is what the multiplication principle gives you: The number of outcomes to a step-wise procedure where you can make $n_i$ possible choices at step $i$. Sometimes this produces exactly one of each of the things you want to count; sometimes it produces exactly $a!$ (say) versions of each of the things you want to count (perhaps because it produces ordered results and you don’t want to count ordered results). Divide by something if and only if the step-wise procedure produces multiple copies of each thing you want to count. With the $A,B,C$ example, it does not. $\endgroup$ – Steve Kass Nov 22 '18 at 0:55

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.