Sixfold way
Become a master of counting!
The sixfold way is an organization of a wide range of counting problems into \(6\) fundamental types. It allows for complicated counting problems to be solved systematically by re-framing them as problems about counting the number of ways to place \(n\) objects into \(m\) distinct boxes. Whether the objects are distinct or identical as well as the restrictions on how to distribute them decide which type applies to a given case. Here's a table of \(6\) ready-to-go solutions for each of the types:
| \(n = \) number of objects \(m = \) number of boxes |
No restrictions | At most one object per box (Requires \(m \geq n\)) |
Same number of objects in each box (Requires \(m \mid n\)) |
|---|---|---|---|
| Indistinguishable objects | $$\binom{n + m - 1}{m - 1}$$(Counting multisets) | $$\binom{m}{n}$$(Counting combinations) | $$1$$ |
| Distinguishable objects | $$m^n$$ | $$P(m, n)$$(Counting permutations) | $$\frac{n!}{((\frac{n}{m})!)^m}$$(Counting permutations with repetition) |
Mastery of the sixfold way can significantly change how you approach counting problems. Admittedly, counting can feel like an impossible task sometimes. However, if you can relate a problem to one of these \(6\) types, the solution can't be far away.
How many ways are there to distribute \(100\) push-ups among the \(7\) days of the week? Let's analyze this problem according to the sixfold way. It looks like there are \(100\) identical objects (each push-up is the same) being distributed among \(7\) distinct boxes (Monday, Tuesday, Wednesday, Thursday, Friday). No restrictions are given, and so the answer must be \(\binom{n + m - 1}{m - 1}\) with \(n = 100\) and \(m = 7\), which is \(\binom{100 + 7 - 1}{7 - 1} = \binom{106}{6}.\)
How many ways can \(4\) unique awards (Best Picture, Best Director, Best Actor, Best Actress) be awarded among \(12\) movies, such that there is no limit on the number of awards each movie can earn? This resembles the distribution of \(4\) distinct objects among \(12\) distinct boxes. Let's step back to the rule of product. There are \(12\) choices for who wins Best Picture, then, after that choice has been made, still \(12\) choices for who wins Best Director, because there is no restriction on how many awards can be earned by a movie. Overall, each of the \(4\) awards has \(12\) choices of recipients. Thus, the answer is \(12 \times 12 \times 12 \times 12 = 12^4\), which is what you get when you plug \(n = 4\) and \(m = 12\) into \(m^n.\)
How many ways can \(5\) officers be elected from a class of \(20\) students? You might quickly notice this is about combinations and guess \(\binom{20}{5}\), which would be correct. So, if you got that without the sixfold way, good job! However, even if you didn't, you can still rely on the sixfold way to relate the problem to objects and boxes. In particular, this problem appears to be involving the distribution of \(5\) identical objects (officer roles) among \(20\) distinct boxes (students). There is an implied restriction that no student can receive the officer role more than once. This translates to each box containing either \(1\) object or no object at all, representative of the fact that each student can either be elected or not. Therefore, we use \(\binom{m}{n}\) with \(n = 5\) and \(m = 20\) (notice \(m \geq n\)) to get \(\binom{20}{5}.\)
How many ways can \(4\) differently-colored dice all show different numbers? If you're comfortable with permutations, you'll answer \(P(6, 4)\) with ease. For the sake of the sixfold way, let's relate this problem to objects and boxes. Since each die can only show \(1\) number, they represent distinct boxes (due to being uniquely colored) limited to holding at most \(1\) object each, with the objects being the numbers \((1, 2, 3, 4, 5, 6)\), which are also distinct. Assigning dice to numbers in order reveals a decreasing number of options: \(6 \times 5 \times 4 \times 3\), which is why the formula \(P(m, n)\) can then be used to obtain \(P(6, 4)\), given \(n = 4\) and \(m = 6.\) Again, notice that \(m \geq n\) here.
How many ways can \(11\) candy bars be distributed among \(5\) kids, such that every kid receives the same number of candy bars? Trick question. The answer is \(0.\) There is no allocation of all \(11\) candy bars among \(5\) kids that results in each kid having the same amount. The problem is that \(5\) does not divide \(11.\) Here's another question. How many ways can \(10\) candy bars be distributed among \(5\) kids, such that every kid receives the same number of candy bars? Since \(5\) divides \(10\), we know it is possible to distribute the candy bars evenly by giving every kid \(2\) candy bars. By comparing the candy bars to identical objects and the kids to distinct boxes, it's clear that there is only \(1\) unique way of distributing these candy bars. It's \(2\) per kid. Swapping any \(2\) candy bars won't have any effect as they are considered identical.
What if the candy bars were all from different brands? Then the question has become: how many ways can \(10\) different candy bars be distributed among \(5\) kids, such that every kid receives the same number of candy bars? It is still true that every kid will receive \(2\), but it now makes a difference which \(2\) in particular each kid receives, as our objects, the candy bars, have now become distinct. First, out of the \(10\) candy bars, choose which \(2\) will go to the first kid. Then, out of the \(8\) remaining, choose which \(2\) go to the second kid, and so on, until all candy bars have been given out. This leads to \(\binom{10}{2} \times \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}\) ways of giving out the distinct candy bars. Multiplying it out, you get \(\frac{10!}{2! \times 2! \times 2! \times 2! \times 2!}\), which matches the formula for permutations with repetition where each element occurs \(\frac{10}{5} = 2\) times, for \(n = 10\) and \(m = 5\): \(\frac{n!}{((\frac{n}{m})!)^m}.\) The answer is therefore \(\frac{10!}{((\frac{10}{5})!)^5} = \frac{10!}{2! \times 2! \times 2! \times 2! \times 2!}.\)