Counting tricks

By Ryan Ng

Combinatorics is the field of mathematics related to counting things efficiently, especially when it is too time-consuming to count each combination with brute force. It is often associated with combinations or probability, but its applications stem far beyond that. This article will showcase some useful counting techniques—from personal experience, these are often highly applicable to school math tests. It makes for a great way to “cheese” questions.

Prerequisites

This assumes you know about factorials and the combination formula.

Dividers

Suppose we are investigating the number of ways we can put 7 bananas that are the same, into 3 different buckets. We could have 4 bananas in the first, 2 in the second, and 1 in the third. We could also have 2 in the first, 4 in the second, and 1 in the third; this would be a different combination. 

This type of question is easily solved with dividers. Let’s first write our 7 bananas as “O”s.

OOOOOOO

Now, let’s insert two “I”s in random positions.

OOIOOIOOO

You may be able to see that we’ve essentially created 3 buckets by defining 2 dividers—the “I”s—between them. There are 2 bananas in the first bucket, 2 in the second, and 3 in the third. We can try a different arrangement:

OIOOOOOOI

Now, we have 1 banana in the first bucket, 6 in the second bucket, and 0 in the last bucket.

This gives us a nice framework to use the combination formula. We have 7 bananas and 2 dividers (because there are 3 buckets). This means we have 9 slots total. Then, we want to pick any 2 of the 9 slots for the dividers to go into. Our answer is therefore “9 choose 2”—which is 36.

We can generalize the formula. For n items and r buckets, the answer is “n + r - 1 choose r”. But I suggest you go through the above process whenever you use it—it’s far better than memorizing a formula.

The double counting argument

In more complicated combinatorics problems, you can often count some quantity in two different ways. Since the quantity must be equal when you count it in both ways, this would allow us to set up an equation.

Example 1: In a school, each student takes exactly three classes, and each class has exactly three students taking it. Prove that the number of students equals the number of classes.

For this example, we can count the number of enrollments of all students in total. Write the number of students as s and the number of classes as c. The first way of counting is—each student takes 3 classes—so the total enrollments is 3 × s. The second way of counting is each class has 3 students taking it—so we get c × 3. As these two quantities are equal, we have 3 × s = c × 3, or s = c. 

Example 2: Fifteen students join a summer course. Every day, three students are on duty after school to clean the classroom. After the course, it was found that every pair of students has been on duty together exactly once. How many days does the course last for?

Suppose d is the number of days the course lasted for. Since 3 students were on duty each day, there was a total of 3 × d “duties”. This is our first way of counting.

Next, see that each pair of students has been on duty together once exactly. This means each of the 15 students goes on duty 14 other different people in total. Finally, since they go on duty in threes, each student goes on duty with 2 others per day. This means each student goes duty for 14/2 = 7 days. 15 students on duty for 7 days is simply 15 × 7 = 105.
Since these two counting methods must be equal, we have 3 × d = 105, or d = 35. The course lasts for 35 days.