Combinatorics is a bit of an odd area of mathematics, especially when you want to explain the field to people outside of mathematics (or any other related field). They ask, “what is Combinatorics” and you reply “mostly counting”. This is a bit of an over simplification but you understand the idea: Combinatorics, according to Encyclopedia Britannica, is a “field of mathematics concerned with problems of selection, arrangement and operation within a finite or discrete system”. So yes, counting.
To demonstrate the nature of Combinatorics, I would like to share a problem presented in one of my classes that caught my attention due to the different style of problem solving compared to other courses such as Calculus. The problem is
How many 4 letter words can be formed from the word LEARNING?
Counting this by hand isn’t a good idea and in general, hard counting in general is not a good idea. Let’s not do that.
The first important clue is noticing that LEARNING contains two Ns which means we need to account for duplicate characters. Luckily, N is the only character with more than one occurrence, greatly simplifying the calculations and steps. Second, notice that we can produce words such as LEAN or NELA but also LEAR or NEAR, which have a different number of Ns. Also recall that we are concerned with arrangements of words, so LEAN is different from NEAL (order matters!). This will influence the steps required to compute the number of words. To summarize:
Clue 1: LEARNING contains Ns
Clue 2: We can make words with 0, 1 or 2 Ns
Clue 3: Order matters
In some ways, this appears to be quite daunting and challenging: there are so many cases to consider. How do we solve such a problem? We can break out problem down into 3 distinct cases and count the cardinality of each case. The 3 cases are as follows:
Case 1: No Ns present
Case 2: One N present
Case 3: Two Ns present
For Case 1: this is quite straight forward. We have 4 letters we wish to pick from LEARIG, so there are 6P4 or 6 Pick 4 or 6 Permute 4. Medium doesn’t support Latex so I’ll just compute the answer. Note that nPk refers to n Pick k (Permutation) and nCk refers to n Choose k (Combination). 6P4 = 360.
For Case 2: we are required to add one N to our possible characters. Now, we have to pick 4 letters from LEARING but we will approach this part slightly differently. Since we are dealing with words (or permutations) that contain ONLY one N, we are only allowed to pick 3 letters. Our Case 2 words generally look like N _ _ _, _ N _ _, _ _ N _ or _ _ _ N. We also need to account for N being in different spots, since, for example, NEAR and ENAR are different words. To account for the different positions, we multiply by 4, since there are 4 potential spots (first letter, second letter, third letter, fourth letter). The total number of Case 2 words are 4*(6P3) = 480.
For Case 3: we are required to add another N, for a total of two Ns, to our possible characters. We have to pick 4 letters but we can think of it in another way. Since Case 3 requires we deal with words with EXACTLY two Ns, we are essentially only allowed to pick 2 letters. For example, suppose we pick E and A from our letters and we wish to add the two Ns. Some possible outcomes are EANN, ENAN or ANEN. First, we can pick 2 letters in 6P2 ways (Non Ns) and pick the spots for the two Ns in 4C2 ways. Since this problem is relatively small, you could count the number of arrangements of spots for the two Ns as it helps with visualization. Finally, the total number of ways to form four-letter words that has exactly two Ns is (6P2)*(6) = 180.
Since we have broken down this problem into three distinct cases, we can add the cardinality (or size) of each case. The total number of 4 letter words that can be formed from the word LEARNING is 360 + 480 + 180 = 1020 words.
This problem was interesting because it makes you think about reducing large problems into smaller simpler cases which can be counted. I guess you could try to count without breaking it down into cases, however, I think that would be quite difficult and confusing, unless you were a robot. Here are some key take points from this problem:
Break the problem into smaller, distinct cases
Combinatorics problems can grow in size dangerously fast!
Counting is key!
Thank you for reading, I hope you learned something. I know I sure did!
