Counting by grouping

80 Views Asked by At

In general could someone explain the difference between the following two approaches?

Say we have $n$ objects split into $r$ groups of sizes $n_1, \ldots n_r$. What is the difference between

$$\frac{n!}{n_1!\cdots n_r!}$$ and $$r!n_1!\cdots n_r!.$$

When is each valid? The first says we have split these objects up by first choosing $n_1$ of them and then $n_2$, etc. The second says we have these groups, we can shuffle them internally ($n_k!$) and we can shuffle the whole groups ($r!$)$. What is the difference?

Example 1: Natalie is taking a multiple choice exam with 20 questions, each of which has four options: A, B, C, and D. There are $4^{20}$ possible ways she can choose one answer for each question. How many of these ways involve exactly 5 questions answered A, 5 questions answered B, 5 questions answered C and 5 questions answered D?

So I'm confused here if this is just

$$\frac{20!}{5!^4}$$ since we are splitting it up into 4 groups of $5$, or if it is actually

$$4!5!^4$$ since we have 4 groups of 5.

Example 2: 8 objects can be arranged in how many ways so that two of them, $A$ and $B$ are together.

is this $8!/2!$? Since we have 6 groups of 1 and a group of 2? or is it $2*7!$?

For further discussion see the comments below.

1

There are 1 best solutions below

0
On

This is long, but a thorough reading should clear any confusion. The first formula $$\frac{n!}{n_1!\cdots n_r!}$$ Gives every single ordering of $n$ elements split into $r$ different groups of identical objects with $n_i$ identical objects in the $i$'th group. An example that may give some insight is ordering the letters $AAABC$. Here there would be $5!$ ways of arranging the elements, except that there are $3$ $A$'s. In any arrangement of $AAABC$, these three $A$'s could be arranged in any of $3!$ different (but identical from the problem's standpoint) orders $$A_1A_2A_3,A_1A_3A_2,A_2A_1A_3,A_2A_3A_1,A_3A_1A_2,A_3A_2A_1$$

The $5!$ accounts for them all. We are not interested in this distinction between $A_1$, $A_2$ and $A_3$ however, so we divide out the $3!$ in order to get the number of different arrangements. We can make the same argument for the $B$ and $C$, dividing out a $1!$, but this doesn't really matter for obvious reasons. Using all of these, however, we can get that the number of ways to arrange $AAABC$ is $$\frac{5!}{(3!)(1!)(1!)}=20$$ In your first example, you are trying to find the number of ways to arrange $AAAAABBBBBCCCCCDDDDD$, so you get $$\frac{20!}{(5!)^4}$$ In your second example, $A$ and $B$ are distinct and stick together, two things wholly unaccounted for by this formula, so it does not apply.

Now for the second formula. This formula describes a sort of shuffling, as you mention, but this shuffling is a very distinctive kind of shuffling. It describes $r$ groups, each with $n_r$ distinct objects. The groups stay together in this shuffling, so after we multiply the shufflings of each individual group, which is $n_1! \cdots n_r!$, and then we shuffle the order of the groups themselves, thus multiplying by another $r!$ to get $$r!n_1!\cdots n_r!$$

In your first example this formula does not apply as there are no groups that are separate from each other. We are trying to find all orderings of $AAAAABBBBBCCCCCDDDDD$, not finding orderings of four groups $AAAAA$, $BBBBB$, $CCCCC$ and $DDDDD$. First off, then we would have streaks of 5 of the same answer in a row. Secondly, these answers are not even distinct, so we can't even begin to apply the second formula.

In your second example, we are ordering $ABCDEFGH$, but we are told $A$ and $B$ are in a group, that is, they cannot be separated. Thus we have seven groups, one is $AB$, and the others are $C$, $D$, $E$, $F$, $G$ and $H$. All letters are distinct here so we can use our second formula, multiplying the number of arrangements of each individual group $(2! (1!)^7)$ by the number of ways of arranging the groups themselves $7!$, so we have $2 \cdot 7!$.