How can I deduce which operation removes redundacies?
Please don't answer by working backwards from the answer, or by appealing to arithmetic. Act as if you're learning this for the first time.
- How can I deduce which operation ought fill in the red blank beneath?
- Why can't it be subtraction?
I shortened the original explanation:
Quandary: How many ways can I give gifts to people, if nobody receives gift?
Explanation: For combinations, order doesn’t matter. This raises an interesting detail of redundancies.
For a moment, let's figure out how many ways we can rearrange 3 people. We've 3 choices for the first person, 2 for the second, and only 1 for the last. So we have ways to re-arrange 3 people. But this is a permutation! If you want to know the number of arrangements for people, it’s just .
So, for giving 3 gifts, there are variations for every choice we pick. To calculate how many combinations, just create all the permutations and $\color{red}\text{_____}$ by all the redundancies. [...]
3 answers
You have 8 people, and you have to pick 3 of them to get identical gifts. Even though the gifts are identical, let's give them labels: A, B, and C. Let's also number the people 1 to 8.
The first step is to figure out how many ways there are to hand out gifts in order. You have 8 choices for gift A, then 7 choices for gift B because you don't want to give to the same person who got gift A, and likewise 6 choices for gift C.
And now we get to the part about redundancies. Let's say for a moment that you gave gift A to person 3, gift B to person 5, and gift C to person 2. Let's call that outcome (3, 5, 2).
From the first step, you know you can make a list of outcomes like the above that is $8\cdot 7 \cdot 6 = 336$ items long. And since that list is all of the ways to give gifts in order to three people, you know that if (3, 5, 2) is on that list, then so is every rearrangement of those three numbers—(5, 3, 2), (2, 5, 3), etc. Because the gifts are identical, you can treat rearrangements as redundant.
So you can imagine organizing your list into groups, where two outcomes belong to the same group if, like (5, 3, 2) and (3, 5, 2), they are rearrangements of each other. (No outcome can belong to more than one group, because rearranging an outcome doesn't change the set of numbers that are in that outcome.) The answer you seek is the number of groups in the list, because each group corresponds to a single not-redundant outcome when all you care about is who gets a gift, not who gets which gift.
Is every group the same size? Yes, because no outcome can use the same number twice (that would mean someone got two gifts), so the numbers must all be different. And there are always $n!$ ways to rearrange $n$ different numbers.
So you have a list of 336 outcomes, organized into groups of size $3! = 6$. How do you determine how many groups there are in the list? Hopefully the answer is now clearer.
0 comment threads
Let's take a look at the computation once more.
The number of ways of arranging $3$ people in a line is $3! = 3 \cdot 2 \cdot 1 = 6$. That is, for any choice of $3$ people from the group of $8$ people, there are $3!$ ways to arrange them in a line. That is, there are $3!$ redundancies per choice of $3$ people. Note the word "per"! If we know the redundancies in arrangements for every (i.e. per) choice of $3$ people, and also the total number of arrangements of $3$ people from the group of $8$, then dividing by the total number of redundancies gives the right answer for the number of combinations.
This is a basic counting principle in combinatorics, that can be stated more generally as follows:
Let $\varphi \colon A \to B$ be a map of finite sets with the property that $\lvert \varphi^{-1}(b) \rvert = k$ (constant) for all $b \in B$. Note that $\varphi^{-1}(b) := \{ a \in A : \varphi(a) = b \}$. Then, $\lvert B \rvert = \lvert A \rvert / k$.
On the other hand, when should we expect to use subtraction instead of division? I will again phrase this in terms of finding sizes of sets (for example, the count of the number of permutations of $k$ objects out of a pool of $n$ objects is just the size of the set of all permutations of $k$ objects out of a pool of $n$ objects).
The basic idea is that if we want to find $\lvert A \rvert$, and $A \subseteq B$, then it is enough to know $\lvert B \rvert$ (the larger total) and $\lvert B \setminus A \rvert$ (the excess), because $\lvert A \rvert = \lvert B \rvert - \lvert B \setminus A \rvert$. In practice, things are rarely so simple. Instead, we have what is known as the "Principle of Inclusion-Exclusion", which in its simplest forms looks like: $$ \begin{gather} \lvert X \cup Y \rvert = \lvert X \rvert + \lvert Y \rvert - \lvert X \cap Y \rvert\\ \lvert X \cup Y \cup Z \rvert = \lvert X \rvert + \lvert Y \rvert + \lvert Z \rvert - \lvert X \cap Y \rvert - \lvert X \cap Z \rvert - \lvert Y \cap Z \rvert + \lvert X \cap Y \cap Z \rvert \end{gather} $$ etc., or a bit more generally, $$ \left\lvert \bigcup_{i = 1}^n X_i \right\rvert = \sum_{\emptyset \neq J \subseteq \{1,\dotsc,n\}} (-1)^{\lvert J \rvert +1} \left\lvert \bigcap_{j \in J} X_j \right\rvert. $$ The Principle of Inclusion-Exclusion is very powerful and has much better formulations than the one I just gave. The Wikipedia page is a decent place to start exploring this topic.
0 comment threads
- How can I deduce which operation ought fill in the red blank beneath?
You can't. It's a hideous phrasing. The issue at question is not "redundancies" (which would carry the implication that they're merely unnecessary) but multiple counting: that is, counting the same assignment more than once.
One way to approach it would be to point out that the original permutation problem can be seen as awarding 1 gold medal, 1 silver medal, 1 bronze medal, and 5 participation certificates. Then we get $8!$ presentation orders, but we reduced to $\frac{8!}{5!}$ distinct ways of assigning the items presented because the participation certificates are equivalent to each other. This isn't a proof of correctness, but it provides a justification for why making the medals equivalent to each other would further reduce to $\frac{8!}{5!3!}$.
To be more formal, take it from
Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re equally disappointed.
The number of ways of ordering Alice, Bob, and Charlie is $3!$ by the same argument as before. So this means that we can cluster the arrangements into groups of $3!$ equivalent arrangements in such a way that each arrangement is in exactly one of the groups. But what we want to count is the number of these groups, or equivalence classes. In this special case where the equivalence classes all have the same size, we can just divide by the size of one equivalence class to get $\frac{1}{3!} \times \frac{8!}{5!}$.
For advanced readers only: in combinatorics we frequently get situations where objects must be grouped in equivalence classes which aren't all the same size. In this more general situation we count by weighting each arrangement by (one divided by the size of its equivalence class).
0 comment threads