Counting

For no particular reason at all, I decided to dig up and study counting from scratch again this week. It took me two full days of solving problems and connecting dots before I could start penning an article that strikes deep at the heart of combinatorics!

The Fundamental Principle of Counting

Let’s imagine that we need to make a pizza and have the following options. $3$ types of crust, $4$ kinds of cheese and 5 different toppings. In how many ways can we make a pizza if we were to choose one type of each ingredient? Since we’re required to choose all three ingredients, we start by mapping each crust to the 4 cheese variants ($3 \times 4 = 12$ ways) and then map each topping to these 12 crust + cheese combinations. This gives us a total of $3 \times 4 \times 5 = 60$ ways to make our pizza. But what if we must either choose a cheese or a topping with our crust and not both? The total number of possible pizza combinations now reduces to $3 \times 4 + 3 \times 5 = 27$. Each crust is now only mapped to either the 4 cheese types or the 5 toppings and those choices are mutually exclusive.

Multiplication is applied while counting sequential events like choosing a crust, then a cheese and finally a topping while addition combines separate events that do not occur together but contribute to the solution space (total number of overall possible events).

Ways of sampling

The number of ways we can sample (pick) $n$ objects $k$ times is simply $n^k$ and is called sampling with replacement. It can be thought as filling $k$ slots in a bag from a pool of $n$ objects (constant) where each slot gets $n$ choices. When a die is rolled twice, there are a total of $36$ different outcomes. This is because for both rolls, we have $6$ possible outcomes (die rolls are independent). The combined outcomes for each event are multiplied according to the fundamental principle. The number of functions possible from a domain of size $5$ and a co-domain of size $6$ is again $6^5$ since each element in the domain can be mapped to 6 different elements in the co-domain and is then repeated 5 times. Another example of sampling with replacement would be to count the number of $5$ character passwords that can be generated using the $26$ letters of the english alphabet and $10$ digits ($0$ to $9$), with no restrictions on repetition. Since there are $(26 + 10 = 36)$ choices for each of the $5$ spots, it leaves us with $36^5$ possible passwords.

The number of ways we can sample $n$ objects without repetition would be $n \times (n - 1) \times (n - 2) ... \times 1$ This is also the number of ways we can arrange (or permute) $n$ objects linearly. This value is known as the factorial and is represented by $n!$

This video has a cool explanation why $0!$ equals $1$.

If our password was now put under a constraint where each character could only be chosen once, we would have $36$ choices for the first character, $35$ for the second and so on till $32$ for the fifth and final character. The total number of possible passwords would now be $36 \times 35 \times 34 \times 33 \times 32$. This result is equivalent to $36!$ divided by $31!$ We call this a permutation or an arrangement of objects where the order matters (ordered sampling without replacement). Simply put, it is the total number of possible arrangements of $n$ objects taken $k$ at a time, with $n!$ being the case when all objects are to be arranged ($n$ objects taken $n$ at a time).

$$\frac{n!}{(n-k)!}$$

Now, if we are asked to find the number of possible combinations of characters (out of 36) that would result in a 5 character password, we have to reject the permutations of the same group of characters. For example, abcde and badce are two different permutations but the same combination of $5$ letters (a, b, c, d, e) as we disregard order and are only concerned about the chosen items (characters in our case) themselves. For this, we divide the total number of permutations by the factorial of the number of objects sampled at a time, which is $k!$

$$\binom{n}{k} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!}$$

This is because every set of size $k$ elements chosen from $n$ has $k!$ permutations and all of those permutations make up $1$ combination. This doesn’t seem very intuitive at first, so let’s demonstrate this with an example.

When looking for combinations, we are partitioning the objects into classes that contain groups (permutations) of the same k-element set. If we have the letters abc, we get $6$ ($3!$) permutations of them.

abc, acb, cab, cba, bac and bca

If our original problem was to count the number of possible combinations of $3$ letter groups from a group of $10$ characters abcdefghij, abc would be a class (of size $k = 3$) that has $3!$ permutations of its own. But since these permutations do not contribute to the total number of distinct combinations, we divide the total number of permutations by $3!$ which gives us $\frac{6}{3!} = 1$ (for each such class).

Each class (of size $k$) has $k!$ different permutations. Thus, dividing the total number of permutations by $k!$ gives us the number of classes (or combinations) since each class corresponds to one combination. This is also known as unordered sampling without replacement.

Grouping

If we want to find the number of ways we can divide $n$ people into $r$ groups of sizes $k_1$, $k_2 ...$ $k_r$ each, we divide the number of permutations of $n$ (which is $n!$) by the factorial of each group size. The intuition behind this is exactly similar to what we discussed earlier.

$$\frac{n!}{k_1! \times k_2! ... \times k_r!}$$

This is called the multinomial coefficient. The binomial coefficient (combination formula) is a special case of the multinomial where $r = 2$ and hence directly leads us to the relation.

$$\binom{n}{k} = \binom{n}{n - k}$$

This means that every time we choose what’s in a subset (of $k$ items) from $n$ items, we are also choosing what’s not in the subset ($n - k$ items). The coefficient tells us that out of $n$ objects, there are $\binom{n}{k}$ possible combinations containing $k$ elements each.

It is important to note that the order of elements within each group does not matter when calculating the number of groupings. For example, suppose we need to divide 8 people into groups of sizes 2, 3, and 3. If these groups are labeled (e.g., specific teams or roles), the number of ways to assign people is given by:

$$\frac{8!}{2!3!3!}$$

However, if the two groups of size 3 are indistinguishable, meaning that swapping them does not create a new arrangement, we are overcounting. In this case, we must divide further by $2!$ and the number of ways to permute the two identical-sized indistinct groups become:

$$\frac{8!}{2!3!3!2!}$$

This adjustment ensures that we do not count the same arrangement multiple times. The key distinction lies not in the individuals within the groups, but in whether the groups themselves are considered distinct or interchangeable based on the context. For example, if the two groups of size 3 represent two named teams, they are considered distinct and no further division is needed. But if the groups are formed randomly and are not functionally different, they are considered indistinguishable and we must account for that by dividing by the factorial of the number of identical groups.

In essence, our multinomial partition is equivalent to first choosing $2$ people out of $8$ and then choosing $3$ people out of the remaining $6$. The last $3$ people are automatically assigned the last group, which we then divide by $2!$ to account for the overcounting of the two groups of $3$.

$$\frac{8!}{2!3!3!2!} = \frac{\binom{8}{2} \times \binom{6}{3}}{2!}$$

It is evident that the presence of identical objects (sampling with repetition) reduce the number of ways we can arrange (or group) them. This leads us to an interesting observation.

When, three dice are rolled, there are 6 possible ways we can get a sum of 9.

$3+3+3\quad2+2+5\quad1+4+4\quad2+3+4\quad1+3+5\quad1+2+6$

and another 6 ways to get a sum of 10.

$3+3+4\quad2+4+4\quad2+2+6\quad2+3+5\quad1+4+5\quad1+3+6$

Even though there are only 6 possible ways for getting both sums, a sum of 10 is more likely than a sum of 9 because the presence of identical elements in an event reduces the total number of permutations.

In both sums, there are 3 events where all the numbers are unique. This gives a total of $3! \times 3 = 18$ possible arrangements for each. In the rest of the three cases, the sum 9 has two events where two numbers are the same $(2,2,5/1,4,4)$ and one event where all three numbers are the same $(3,3,3)$. This gives a combined total of $18 + \frac{3!}{2!} \times 2 + \frac{3!}{3!} = 25$ possible arrangements. For a sum of 10, all the remaining three events have two similar numbers (3,3,4/2,4,4/2,2,6). This gives a combined total of $18 + \frac{3}{2!} \times 3 = 27$ possible arrangements. The presence of $(3,3,3)$ in 9 reduces the permutation space and makes all the difference. Since there is only one way it can be arranged, the probability of getting 3 in all three die rolls is three times less than an event with only two similar numbers ($\frac{3!}{2!}$ ways) and six times less than the event where all three numbers are unique ($3!$ ways). The higher the number of possible permutations, the higher the probability.

Similarity and uniqueness

Let’s pose a question. What is the number of subsets possible from a set of $n$ distinct objects? We can think of it as having the binary choice of either choosing or discarding an object from our set for each of our slots. Since there are $2$ options and $n$ objects (or slots), it gives us a total of $2^n$ possible subsets including the null subset where no objects are chosen. If you have used bitmasking in digital electronics or programming, this should be something you’re already familiar with.

$$\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$$

But what happens when all $n$ items are the identical? How many subsets can we form now? The fact that the objects are now similar changes everything. The total number of ways we can now make a selection from this set will range from $0$ to $n$ or $n + 1$ ways (pick either $0$ items, $1$ item, … all $n$ items). The reason for this is when the objects are distinct, picking two objects (say $A$ and $B$) is not the same as picking two other objects ($C$ and $D$). But when the objects are alike, it makes no difference in which objects we pick. We are only concerned about the number of objects chosen, not their quality.

So if there are 5 chocolates of one type and 3 of another, the total number of ways we can make a selection is $(5 + 1)(3 + 1) = 24.$

The Inclusion-Exclusion Principle

This is an extremely powerful technique that allows us to find the union of sets by avoiding double counting. Let’s understand what this means. Consider two sets $A$ and $B$ that represent the number of students who like the subjects mathematics and chemistry respectively. Say set $A$ has $7$ students and set $B$ has $5$. In both of these sets, there may be students who like both mathematics and chemistry. Now, if we were to find the total number of students who like these two subjects (not the number of students who like both, which is an intersection of the sets), we would consider any student who likes either maths or chemistry. But we cannot simply add the number of students in both sets ($7 + 5 = 12$) as these sets are not necessarily disjoint or mutually exclusive and may contain students who like both the subjects. Hence, the number of students in the union set would certainly be less than $12$. To avoid double counting the students who fall into both sets, we subtract the number of students in the intersection set (say $3$) from the total sum ($12$).

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

This is the very idea behind inclusion-exclusion. We include and exclude combinations of sets to take care of the overlap during counting.

If we were to extend this idea to $3$ sets, we would first add all the single sets, then subtract all the combinations of the intersection of two sets and finally add all the combinations of the intersections of three sets (of which only $1$ exists). This is because in subtracting $A \cap B$ and $B \cap C$, we double subtract the elements in set $B$. The same can be said for $A$ while subtracting $A \cap B$ and $C \cap A$, and C for $B \cap C$ and $C \cap A$.

Below is the union of four sets using inclusion-exclusion. We alternate our signs (add and subtract) on each step till we reach the final intersection of all sets.

$$n(A \cup B \cup C \cup D) = n(A) + n(B) + n(C) + n(D) - n(A \cap B) - n(A \cap C) - n(A \cap D) - n(B \cap C) - n(B \cap D) - n(C \cap D) + n(A \cap B \cap C) + n(A \cap B \cap D) + n(A \cap C \cap D) + n(B \cap C \cap D) - n(A \cap B \cap C \cap D)$$

A great example of applying this knowledge can be found when we’re asked to count the number of onto functions (functions whose range $=$ co-domain, in other words every element in the co-domain must be mapped to an element in the domain) possible from a domain of 5 elements and a co-domain of 6. To begin with, we count the total number of functions possible from these two sets, which is $6^5$ (as discussed earlier). We now proceed to subtract the functions that are not onto. The number of functions where one element in the co-domain is left out can be calculated as $5^5 \times \binom{6}{1}$ since there are $\binom{6}{1}$ ways to choose that one element to leave out. This is equivalent to summing all single sets.

$$\sum_{} A_i$$

Similarly, the rest of the cases (functions where 2 elements are left out and so on) can be represented as

$$\sum_{} | A_i \cap A_j | = 4^5 \times \binom{6}{2} \\ \sum_{} | A_i \cap A_j \cap A_k | = 3^5 \times \binom{6}{3} \\ \sum_{} | A_i \cap A_j \cap A_k \cap A_l | = 2^5 \times \binom{6}{4} \\ \sum_{} | A_i \cap A_j \cap A_k \cap A_l \cap A_m | = 1^5 \times \binom{6}{5}$$

We add and subtract all of these terms alternatively from the total number of possible functions to get the right answer.

Derangement

This is a perfect time to talk about derangement, which is the peculiar arrangement where no element is at their original slot. If we have the set $\{1, 2, 3, 4, 5\}$, then $\{2, 1, 4, 5, 3\}$ would be an example of a derangement whereas $\{2, 1, 3, 5, 4\}$ is not. Let’s consider a set $A_i$ as the permutation where the i-th element is fixed in its original position. Taking an example where we apply derangement to $4$ objects, we start by calculating the total number of possible arrangements ($4! = 24$) and apply inclusion-exclusion to this value. We first calculate the sum of the single sets where one object is fixed. There are $\binom{4}{1}$ ways to choose an item and $3!$ ways to arrange the rest. So we get,

$\sum{}A_i = \binom{4}{1} \times 3! = 24$

But notice that these also include the cases where $2$ or more items are at their correct positions (we are double-counting). To resolve this, we subtract the cases where two objects are at their fixed positions.

$\sum{}A_i - \sum{}|A_i \cap A_j| = 24 - \binom{4}{2} \times 2! = 12$

But again, this also includes subtracting the cases where $3$ or more items are at their correct positions multiple times (we are over-correcting).

So we add back the case where three sets intersect.

$\sum{}A_i - \sum{}|A_i \cap A_j| + \sum{}|A_i \cap A_j \cap A_k| = 12 + \binom{4}{3} \times 1! = 16$

And finally, subtract the case where all four elements are at their original slot.

$\sum{}A_i - \sum{}|A_i \cap A_j| + \sum{}|A_i \cap A_j \cap A_k| - \sum{}|A_i \cap A_j \cap A_k \cap A_l| = 16 - \binom{4}{4} \times 0! = 15$

We subtract these $15$ invalid permutations from $24$ to get $9$ as the answer. (Same as alternate add/subtract from total possible arrangements)

Adding and subtracting resolves the double-counting and over-correcting introduced by the previous steps respectively.

Integral solutions

We now come to what’s arguably the most tricky sampling scenario. Let’s take the case where we have a set of $3$ ($n = 3$) elements $\{a_1, a_2, a_3\}$ and we need to sample $2$ elements ($k = 2$) such that each element can be picked multiple times (sampling with replacement) and the order does not matter. The elements are identical and the slots are distinct.

$$a_1a_1 \quad a_2a_2 \quad a_1a_3 \quad a_2a_2 \quad a_2a_3 \quad a_3a_3 \quad$$

Clearly, there are $6$ possible ways of making a selection. To arrive at this solution mathematically, we can represent each of those solutions as a vector of size $n$ that sums up to $k$ where the element at position $i$ represents the number of times the $i$th item of the set has been sampled.

$$a_1a_1 - (2, 0, 0) \\ a_2a_2 - (1, 1, 0) \\ a_1a_3 - (1, 0, 1) \\ a_2a_2 - (0, 2, 0) \\ a_2a_3 - (0, 1, 1) \\ a_3a_3 - (0, 0, 2)$$

This is equivalent to finding the number of positive integral solutions of the equation

$$x_1 + x_2 + x_3 = 2; \quad x_i \ge 0$$

In general, the number of integral solutions of the equation $x_1 + x_2 + \dots + x_n = k$ is given by

$$\binom{n + k - 1}{k}$$

The intuition behind this is deceptively simple. Let’s imagine the situation where we need to distribute $5$ chocolates ($k = 5$) to $3$ ($n = 3$) kids. One possible solution could be:

$$a_1 \quad a_2 \quad | \quad a_3 \quad | \quad a_4 \quad a_5$$

For each such solution, we always place $k$ chocolates and $n - 1$ bars to partition them into $n$ bins (children), which gives us a total of $n + k - 1$ positions. We only need to choose $n - 1$ positions for the bars and the rest of the positions will be assigned to the chocolates (items). This gives us $\binom{n + k - 1}{n - 1} = \binom{n + k - 1}{k}$.

This method is equivalent to arranging (or grouping) $n + k - 1$ items using the multinomial coefficient where $k$ items are of one kind and $n - 1$ are of another.

$$\frac{(n + k - 1)!}{(n - 1)! \times k!}$$

Adding constraints

Our distribution problem can be complicated by adding a constraint on one or more variables. If we take the equation,

$$x_1 + x_2 + x_3 = 10; \quad x_1 \ge 1, x_2 \ge 2$$

this becomes a problem where $10$ chocolates must be distributed to $3$ kids where the first kid must be given at least $1$ chocolate and the second kid must have at least $2$ (Same as the number of ways we can get a sum of $10$ when $3$ dice are rolled). To solve this, we need to substitute the constraint variables with $x_1'$ and $x_2'$ where $x_1' = x_1 - 1$ and $x_2' = x_2 - 2$. This is because the least possible values of $x_1$ and $x_2$ must be 1 and 2. So the equation now becomes:

$$x_1' + x_2' + x_3' = 10 - (1 + 2); \quad x_3' = x_3 \\$$

If the constraint on $x_1$ was $x_1 \gt 1$, then $x_1' = x_1 - 2$ since $2$ is the smallest possible value $x_1$ can take.

Let’s now consider the equation with the following constraints:

$$x_1 + x_2 + x_3 + x_4 = 12; \quad 2 \le x_1 \le 5; \quad 0 \le x_2 \le 4 \quad 1 \le x_3 \le 3 \quad 0 \le x_4 \le 6$$

Although it might seem intimidating, our knowledge of inclusion-exclusion will allow us to solve this fairly easily.

Let’s start by taking care of the lower bounds of each variable and shift our variables accordingly.

$$x_1' + 2 + x_2' + 0 + x_3' + 1 + x_4' + 0 = 12 \\ \quad \\ x_1' + x_2' + x_3' + x_4' = 9$$

The number of solutions of this transformed equation is equal to $\binom{9 + 4 - 1}{4 - 1} = \binom{12}{3} = 220$

We now shift our attention to the upper bounds. Since we have shifted each variable by their minimum constraint, their range has now become the following:

$$x_1' \in [0, 3] \implies [0, 5 - 2] \\ x_2' \in [0, 4] \implies [0, 4 - 0] \\ x_3' \in [0, 2] \implies [0, 3 - 1] \\ x_4' \in [0, 6] \implies [0, 6 - 0] \\$$

Hence, the maximum possible value for each variable now becomes $3, 4, 2$ and $6$ respectively. To apply inclusion-exclusion, we first eliminate (subtract) all the possible solutions that contain the following values

$$x_1 \ge 3 + 1; \quad x_2 \ge 4 + 1; \quad x_3 \ge 2 + 1; \quad x_4 \ge 6 + 1$$

one at a time as they are all invalid. This is analogous to the sum of all the single sets $\sum{} A_i$

$$x_1' \implies \binom{(9 - 4) + 3}{3} = 56; \quad x_2' \implies \binom{(9 - 5) + 3}{3} = 35; \quad x_3' \implies \binom{(9 - 3) + 3}{3} = 84; \quad x_4' \implies \binom{(9 - 7) + 3}{3} = 10 \quad$$

whose sum equals $56 + 35 + 84 + 10 = 185.$ Following this, we move to the second step where we now consider every pair of constraint variables.

$$(x_1, x_2) = (4, 5) = \binom{(9 - 9) + 3}{3} = 1; \quad (x_1, x_3) = (4, 3) = \binom{(9 - 7) + 3}{3} = 10; \quad (x_1, x_4) = (4, 7) = 11 > 9 = 0; \quad (x_2, x_3) = (5, 3) = \binom{(9 - 8) + 3}{3} = 4; \quad (x_2, x_4) = (5, 7) = 12 > 9 = 0; \quad (x_3, x_4) = (3, 7) = 10 > 9 = 0 \quad$$

The sum of these pairs $\sum{}|A_i \cap A_j|$ equals $15$. Finally, the combinations of triplets and quadruplets would result in zero possible solutions.

Applying alternate summation, we get $220 - 185 + 15 = 50$ solutions.

Identical Slots

The case of identical slots is rather cumbersome. Let’s take the scenario where we have $6$ distinct books that we want to place into $4$ identical boxes so that each box can get either $0$ or more books. If the boxes were distinct, we’d simply say that there are $4^6$ ways of distributing and be done with it. Putting a book $T_1$ into box $A$ and book $T_2$ into box $B$ is not the same as the opposite ($T_1$ into $B$ and $T_2$ into $A$) and are counted separately. But when the boxes are identical, this isn’t true because the boxes are not labelled and hence their order does not matter anymore. Since there is no way to tell the boxes apart, the two cases “collapse” into one single case.

The former can be considered as mapping functions from a domain and co-domain while the latter is a case of integer partitioning.

To solve our problem, we start by considering the distinct partitions of the books into the 4 boxes like so.

$$6 + 0 + 0 + 0 \\ \quad \\ 5 + 1 + 0 + 0 \\ \quad \\ 4 + 2 + 0 + 0 \\ \quad \\ 4 + 1 + 1 + 0 \\ \quad \\ 3 + 3 + 0 + 0 \\ \quad \\ 3 + 2 + 1 + 0 \\ \quad \\ 3 + 1 + 1 + 1 \\ \quad \\ 2 + 2 + 2 + 0 \\ \quad \\ 2 + 2 + 1 + 1 \\$$

If we use grouping (multinomial coefficient) for each case, we get:

$$6 + 0 + 0 + 0 = \frac{6!}{6!} = 1 \\ \quad \\ 5 + 1 + 0 + 0 = \frac{6!}{5!1!} = 6 \\ \quad \\ 4 + 2 + 0 + 0 = \frac{6!}{4!2!} = 15 \\ \quad \\ 4 + 1 + 1 + 0 = \frac{6!}{4!1!1! \times 2!} = 15 \\ \quad \\ 3 + 3 + 0 + 0 = \frac{6!}{3!3! \times 2!} = 10 \\ \quad \\ 3 + 2 + 1 + 0 = \frac{6!}{3!2!1!} = 60 \\ \quad \\ 3 + 1 + 1 + 1 = \frac{6!}{3!1!1!1! \times 3!} = 20 \\ \quad \\ 2 + 2 + 2 + 0 = \frac{6!}{2!2!2! \times 3!} = 15 \\ \quad \\ 2 + 2 + 1 + 1 = \frac{6!}{2!2!1!1! \times 2!2!} = 45 \\$$

Summing all the cases gives us a total of $187$ ways.

Finally, if both our books and boxes were taken to be identical, we would just have those 9 ways of integer partitioning for our answer.

Symmetry in arrangements

In a linear arrangement, we have a specified start and end to the sequence. For instance, abcd and cdba are two permutations where the first and last elements of the arrangements are obvious and concrete. But what happens when we arrange them in a circle? The start or end of such an arrangement reduces to perspective. So what really matters is the relative order of the objects since a rotation of the circle would not result in a new arrangement. In order to break this symmetry, we first place 1 element at 1 spot (1 way) and then the rest $n - 1$ elements in $(n - 1)!$ ways by taking the first item as reference. Thus, the number of circular permutations of $n$ objects become $(n - 1)!$

An interesting case of circular arrangements arise from the arrangement of beads on a necklace. Apart from the usual rotational symmetry, the reflectional symmetry is also considered where the necklace is flipped along an axis. This means that half of the unique arrangements that we get from a normal circular arrangement are not distinct anymore. Due to this, we divide the total number of arrangements by $2$.

Burnside’s Lemma

But the story doesn’t end there. In fact, it gets a whole lot complicated when we consider the possibility where some beads are not distinct. This means that there will be many arrangements that reduce or collapse to a single arrangement when a rotation or reflection is performed on them. Each group of such arrangements that represent that same rotation/reflection symmetry is called an orbit.

Burnside’s Lemma states that the number of such orbits (equal to the number of truly distinct arrangement of necklaces) is equal to the sum of the fixes contributed by each transformation divided by the number of rotations/flips performed on the necklace. Do not worry about the use of jargon as we will clear it all up with a detailed example.

A fix is simply an arrangement that stays unchanged (fixed) under a transformation (rotation/reflection). Let’s take the example of a necklace with 4 beads and 2 colours (represented by A and B) to really understand this.

The number of ways we can colour this necklace is $2^4$.

AAAA, AAAB, AABA, AABB, ABAA, ABAB, ABBA, ABBB, BAAA, BAAB, BABA, BABB, BBAA, BBAB, BBBA, BBBB

Now, the total number of transformations we can perform on this necklace is $8$ (Rotations: $0\degree, 90\degree, 180\degree, 270\degree$) + (Reflections: $2$ through opposite beads, $2$ through opposite gaps).

If we consider the rotation transformation of $90 \degree$, there are only two colourings that do not change. (AAAA and BBBB). Thus, the fix for this transformation (fix[$90 \degree$]) is $2$. Similarly, if we take the $180 \degree$ transformation, the colourings that stay the same are AAAA, ABAB, BABA, BBBB and its fix is $4$. If we repeat this process for all transformations and divide the sum of all the fixes by the number of transformations, we get the number of orbits or in other words, the number of distinct colourings that are completely asymmetric with each other.

$$O = \frac{\sum{}{fix(g)}}{|G|_{g \in G}}$$

This division (or averaging) accounts for the double counting that is present across all transformations. (e.g. $90\degree$ and $270\degree$ both have the same $4$ arrangements)

This lemma finds its use in unlabelled graph enumeration problems and even in chemistry to count isomers of a compound.

It can also be used to solve the problem from the Identical Slots section in a similar way!

Although it’s awfully difficult to get a grasp of this lemma without self-experimentation and visualization, I hope I did a decent job at explaining this without delving into group theory and theoretical shenanigans!

Geometry

Here are a few common ways combinatorics is used in geometry.

• If we have a set of $n$ points, the maximum number of line segments that can be formed is simply $\binom{n}{2}$ as we are counting the number of possible groups of $2$ points. This idea can also be used to count the number of diagonals in an $n$ sided polygon. We first count the number of ways we can select $2$ points from $n$ and then subtract $n$ from it to avoid counting the sides of the polygon.

  $$\binom{n}{2} - n = \frac{n(n - 3)}{2}$$

• The number of ways $n$ shapes can intersect is $\binom{n}{2}$ times the maximum number of intersection points formed when two of those shapes intersect ($m$), given that all intersections are pairwise i.e no point is common to more than two shapes. $\binom{n}{2} \times m$ is a good upper bound if our assumptions are followed.

• In general, the number of $k$ sided polygons we can form from a set of $n$ points is given by $\binom{n}{k}$. But in the presence of collinear points, we have a case of overcounting. This is where our old friend inclusion-exclusion comes to aid. Let’s say there are $A_1, A_2 \dots A_m$ collinear sets where set $A_i$ has $k_i$ collinear points. We then subtract the number of possible polygon pairs for each set from our naive solution as collinear points do not form a polygon. Let’s illustrate this with an example. Say we have $12$ points ($n = 12$) and three sets of collinear points $A_1 = \{1, 2, 3, 4\}$, $A_2 = \{4, 5, 6\}$, $A_3 = \{7, 8\}$. The number of triangles we can form naively are $\binom{12}{3} = 220$. The first set currently contributes to $\binom{4}{3} = 4$ “triangles” which are invalid. Similarly, the second contributes to $\binom{3}{3} = 1$ “triangle” and the last set does not contribute to any. Our revised answer is $220 - 4 - 1 = 215$. Even though there exists a shared point between $A_1$ and $A_2$ (${4}$), the overlap cannot affect our solution (Can you think why?). In case of line segments, each set contributes to only 1 line so we add the number of collinear sets back at the end.

Conclusion

If you made it this far, I must commend you for your grit. You might have realized by now that solving most combinatorics problems rely on understanding the nuances and constraints instead of a magical formula that can be applied naively. Learning and building the intuition behind applied mathematics is an incredibly fulfilling experience if carried out with diligence. This is why I like to believe that the factorial symbol was a consequence of the mathematicians’ astonishment.