Unit 6: Combinatorics

Overview

In this unit, we will start moving onto topics that are very distinct from proofs and far closer to the traditional topics in math that are useful in computer science. To do this, we will first begin with combinatorics! Think of this as an advanced way of counting. The reason why this is useful is because when it comes to analysing certain mathematical constructs, or when it comes to counting how many cases our programs have to deal with, the techniques here the ones we fall back on.

We have broken this unit up into 4 parts:

1. Basic Counting
2. Principle of Inclusion-Exclusion
3. Permutations and Combinations
4. Applying Combinatorics for Problem Solving

Counting Based on Sets

Let’s begin by simplifying things a little bit, for now let’s just count items in sets. Since we are counting, we need to talk about the size of sets. So given a set $A$, the size of a set is written as $|A|$.

So for example: $|\{a,b,2,100\}|=4$ since this set has $4$ items. Also since $\varnothing$ is empty, this means that it holds no items, so $|\varnothing |=0$. We won’t consider infinitely sized sets, so we won’t be talking about what $|\mathbb{Z}|$ is.

Basic Counting Techniques

So let’s start with the most general ideas that will be repeated for the next few weeks: adding disjoint and multiplying successive choices.

Rule of Sum: Adding Disjoint Cases

Let’s say we had two sets, $A$ and $B$ that had no common elements. That is to say, $A\cap B=\varnothing$. We call these two sets disjoint.

So what is the size of $A\cup B$? In other words, if we knew three things:

1. $|A|=m$
2. $|B|=n$
3. $A\cap B=\varnothing$

What is $|A\cup B|$? Well, $|A\cup B|=m+n$.

Example

Let $A=\{1,2,3,4\}$ and $B=\{10,11,12\}$. Then $A\cap B=\varnothing$. So $|A|+|B|=4+3=7$.

Example

Let $A=\varnothing$ and $B=\{10,11,12\}$. Then $A\cap B=\varnothing$. So $|A|+|B|=0+3=3$.

What about in general? What if we had $3$ sets? What if we had $10$ sets? What should the condition be? This is a little subtle.

Let’s try this for $3$ sets. Let’s say we had $3$ sets $A,B,C$ for which:

1. $|A|=m$
2. $|B|=n$
3. $|C|=\ell$
4. $A\cap B\cap C=\varnothing$

Can we conclude that $|A\cup B\cup C|=m+n+\ell$? Feels very tempting for us to conclude so, after all the sets are disjoint right?

What about the following example of sets?

$A=\{2,4,6\}$, $B=\{3,6\}$, $C=\{3,5\}$. Now notice that $A\cap B\cap C=\varnothing$. Check it! There is not a single element that is in all $3$ sets!

1. $2\notin C$
2. $3\notin A$
3. $4\notin B$
4. $5\notin B$
5. $6\notin C$

So $|A|=3$, $|B|=|C|=2$. So we expect $3+2+2=7$ elements. But $|A\cup B\cup C|=5$. So our condition here isn’t quite right. Where did we go wrong?

Let’s think of it this way. We want to use the fact that when $2$ sets are disjoint, we can just add their sizes together. How should we use this to work on $3$ sets? Let’s consider an alternative set of conditions:

1. $|A|=m$
2. $|B|=n$
3. $|C|=\ell$
4. $A\cap B=\varnothing$
5. $A\cap C=\varnothing$
6. $B\cap C=\varnothing$

From conditions 4, 5, and 6, we can derive the following lemma:

Lemma 1:

$$\begin{array}{rl}(A\cup B)\cap C& =(A\cap C)\cup (B\cap C)\\ & =\varnothing \cup \varnothing \\ & =\varnothing \end{array}$$

So what does this mean? It means that the set $A\cup B$ and the set $C$ is disjoint! This means that $|(A\cup B)\cup C|=|(A\cup B)|+|C|$.

So let’s try counting again:

$$\begin{array}{rl}|A\cup B\cup C|& =|(A\cup B)\cup C|\\ & =|(A\cup B)|+|C|\\ & =|A|+|B|+|C|\end{array}$$

Now it works! So what about between more sets? Here’s the general statement:

Given $n$ sets $A_1,A_2,A_3,\dots ,A_n$, such that:

1. $\forall i\in [n]$, $|A_i|=s_i$ (the $i^{th}$ set has size $s_i$)
2. $\forall i\in [n]$, $\forall j\in [n]$, if $i\ne j$, then $A_i\cap A_j=\varnothing$ (any two distinct sets are disjoint)

Then, ${\sum }_{i=1}^n{s}_i=|A_1\cup A_2\cup A_3\cup \cdots \cup A_n|$. The size of the all of the sets is just their individual sizes added up.

Conclusion: So what’s the conclusion here? Think of it this way, when we could make either choices from set $A$ or choices from set $B$, where $A$ and $B$ are disjoint. Then we can just add them up.

Rule of Product: Multiplying Successive Choices

Okay, what about considering making a sequence of choices? Given two sets $A$, $B$ (this time not necessarily disjoint), how do we count how many ways are there to make a choice from $A$ and then a choice from $B$?

This one is a little more straightforward. After all, we’ve actually made sets that actually represent this!

To make a choice from $A$ and then a choice from $B$ is to ask, how many pairs there are from $A$ and then $B$, i.e.,

$$\begin{array}{r}A\times B\end{array}$$

So we are essentially asking: what is the size of $A\times B$? And this is pretty much just $|A|\times |B|$.

Example

Let $A=\{1,2,3,4\}$ and $B=\{1,3\}$. Then $A\times B=\{(1,1),(1,3),(2,1),(2,3),(3,1),(3,3),(4,1),(4,3)\}$.

$|A|=4$, $|B|=2$, and $|A\times B|=4\times 2=8$.

Example

Let $A=\{1,2,3,4\}$ and $B=\varnothing$. Then $A\times B=\varnothing$.

$|A|=4$, $|B|=0$, and $|A\times B|=4\times 0=0$.

This one is far less involved. Here’s the general statement:

Given $n$ sets $A_1,A_2,A_3,\dots ,A_n$, then:

1. $\forall i\in [n]$, $|A_i|=s_i$ (the $i^{th}$ set has size $s_i$)

Then, ${\prod }_{i=1}^n{s}_i=|A_1\times A_2\times A_3\times \cdots \times A_n|$. The size of the all of the sets is just their individual sizes multiplied.

Counting Subsets

Let’s see a simple and repeated application of the rule of product. Let’s say we had a set $A$ such that $|A|=n$. How many elements are in $\mathcal{P}(A)$? I.e. how many subsets are there?

Let’s lay out the $n$ elements of $A$ as $a_1,a_2,\dots ,a_n$. Notice that for each of these elements, we can make a choice of “take” or “don’t take”. And for any sequence of $n$ choices, this creates for us a subset of $A$.

For example, if $A=\{1,2,3\}$, then a sequence like “take”, “don’t take”, “take” will create a subset $\{1,3\}$. Whereas a sequence like “don’t take”, “don’t take”, “don’t take” creates the subset $\varnothing$.

We can think of this as making a set $C=\{\text{take},\text{don’t take}\}$. And we are basically asking what is:

$$\underset{n\text{ many times}}{\underbrace{|C\times C\times \cdots \times C|}}$$

By the rule of product, we know this is:

$$\underset{n\text{ many times}}{\underbrace{|C\times C\times \cdots \times C|}}=\underset{n\text{ many times}}{\underbrace{|C|\times |C|\times \cdots \times |C|}}$$

We know that $|C|=2$. So the above is basically:

$$\underset{n\text{ many times}}{\underbrace{|C|\times |C|\times \cdots \times |C|}}=2^n$$

So $|\mathcal{P}(A)|=2^{|A|}$.

Rule of Division

So while the previous two laws might be a little clearer, there’s one less common one that is based on a nice trick. Let’s try this with a scenario:

Let’s say it was right after the midterm, and we have just collected a bunch of exam scripts. We know each script has the same number of pages to scan, $8$ pages. We put our entire stack of exam scripts in the scanner, and the scanner reports there are $104$ pages scanned.

How many scripts have we scanned? Since each script had $8$ pages, this means there were $104÷8$ scripts.

This might sound a little obvious, but this trick can be taken to extremes eventually in the subsequent sections.

In general, if we have $n$ items, but we are able to group $k$ of them into groups where we think they are identical, then we have $n/k$ groups.

Subtracting Cases

One more useful idea is when we have two sets $A,B$ and we are promised that $B\subseteq A$. Then, we know that:

$$|A\setminus B|=|A|-|B|$$

Counting Consecutive Numbers

The last of the basic counting facts is the following: given a set of integers that are at least $a$, and at most $b$, i.e.,

$$\{x\in \mathbb{Z}:a\le x\wedge x\le b\}$$

How many integers are there? It’s very tempting to say $b-a$, but the actual answer is $b-a+1$.

For example, there are $6-2+1=5$ integers in the set $\{2,3,4,5,6\}$.

Counting Multiples

What about if we wanted to count numbers divisible by some number $d$ within some range $[a,b]$?

This is a little tricky. Let’s try a simpler idea:

Given a positive number $a$, how many numbers in the range $[1,a]$ are there that are divisible by $d$? Well, there are $a$ numbers in that range, so that would be:

$$\lfloor \frac{a}{d}\rfloor$$

If we instead wanted the numbers in the range $[0,a]$ that are divisible by $d$, then this becomes:

$$\lfloor \frac{a}{d}\rfloor +1$$

because $0$ is divisible by any number (including $d$).

What we if wanted to count numbers between $[a,b]$ (inclusive) that are divisible by $d$? Now we can use the idea from Subtracting Cases! Notice we are counting the numbers from $[0,b]$ that are divisible by $d$, then subtracting away the numbers from $[0,a-1]$ that are divisible by $d$. Which gives us:

$$\lfloor \frac{b}{d}\rfloor +1-\left(\lfloor \frac{a-1}{d}\rfloor +1\right)=\lfloor \frac{b}{d}\rfloor -\lfloor \frac{a-1}{d}\rfloor$$

Let’s test out the formula.

Example

For example, how many numbers are there divisible by $3$ in the range $[5,12]$? There are $6,9,12$. $\lfloor \frac{12}{3}\rfloor -\lfloor \frac{5-1}{3}\rfloor =4-1=3$.

Example

For example, how many numbers are there divisible by $5$ in the range $[5,36]$? There are $5,10,15,20,25,30,35$. $\lfloor \frac{36}{5}\rfloor -\lfloor \frac{5-1}{5}\rfloor =7-0=7$.

Example

What about if we asked how many numbers are divisible by $2$ in the range $[0,9]$? There should be $5$ of them: $0,2,4,6,8$.

$\lfloor \frac{9}{2}\rfloor -\lfloor \frac{0-1}{2}\rfloor =4-(-1)=5$.

Principle of Inclusion-Exclusion

Sticking to the topic of counting sets for now, can we be a little more precise in counting $|A\cup B|$? There actually is a formula for this!

$$|A\cup B|=|A|+|B|-|A\cap B|$$

Example

Let $A=\{2,4,6\}$, $B=\{3,6\}$. Then $A\cap B=\{6\}$.

Then $|A|=3$, $|B|=2$, and $|A\cap B|=1$. Then $|A\cup B|=3+2-1=4$.

Why does this work? Because the idea is that if we just add $|A|$ and $|B|$, we’re double counting the elements in $|A\cap B|$, since they will be added once due to $|A|$, then added once again in $|B|$.

In fact, this tells us why the additive rule works when $A$ and $B$ are disjoint. Because in that case, $|A\cap B|=0$.

This technique alone is quite useful. Here is an example that makes use of this idea.

Example:

Here’s a question: How many $1$-digit numbers are there that are divisible by $2$ or $3$? So this is simple enough that we could have manually counted this: $0,2,3,4,6,8,9$.

For this example we’re picking $1$-digit numbers because it makes it easy for us to verify that we’re indeed correct. This becomes very infeasible if we wanted to do this for $3$-digit numbers and so on.

But we could have made $2$ sets, $A=\{x\in \mathbb{Z}:0\le x\le 9\wedge divides(2,x)\}$, and $B=\{x\in \mathbb{Z}:0\le x\le 9\wedge divides(2,x)\}$. Then asked what is $|A\cup B|$?

So let’s compute $|A|$, $|B|$, and $|A\cap B|$. The first $2$ numbers are computed based on Counting Multiples.

For $A$, as before:

$$|A|=\lfloor \frac{9}{2}\rfloor -\lfloor \frac{0-1}{2}\rfloor =4-(-1)=5$$

For $B$:

$$|B|=\lfloor \frac{9}{3}\rfloor -\lfloor \frac{0-1}{3}\rfloor =3-(-1)=4$$

And for $A\cap B$, we want the numbers that are divisible by both $2$ and $3$. In other words, divisible, by $6$. So:

$$|A\cap B|=\lfloor \frac{9}{6}\rfloor -\lfloor \frac{0-1}{6}\rfloor =1-(-1)=2$$

So now, we can figure out $|A\cup B|=5+4-2=7$.

Follow-Up 1:

What if we wanted to count the $1$-digit numbers that were not divisible by $3$, and not divisible by $2$? In other words, we want to see how many numbers are in $[0,9]$ and not in $A\cup B$. Notice again that $A\cup B\subseteq [0,9]$. So again, through Subtracting Cases, we really just want $\left|[0,9]\setminus (A\cup B)\right|$. Which happens to be:

$$(9-0+1)-7=3$$

Follow-Up 2:

What if we changed the question to: how many $1$-digit numbers are there that are divisible by $2$ and $4$? If we made set $A$ the numbers in the range $[0,9]$ that are divisible by $2$, and $B$ the set of integers in the range $[0,9]$ that are divisible by $4$.

But what should $A\cap B$ be? Should we take this to be $8$? No, we want numbers that are divisible by $2$ and $4$, which happens to be numbers that are divisible by $4$. In fact, we can check this: $A=\{0,2,4,6,8\}$ and $B=\{0,4,8\}$. And of course, $A\cap B=\{0,4,8\}$.

So, in general, how do we determine the divisibility condition for the set $A\cap B$? If set $A$ contains integers that are divisible by $x$, and set $B$ contains integers that are divisible by $y$, then for $A\cap B$, we want integers divisible by both $x$ and $y$. These are the integers that are divisible by the lowest common multiple of $x$ and $y$.

So if $x=2$, $y=3$, we want $lcm(2,3)=6$, since $6$ is the smallest multiple of both $2$ and $3$. On the other hand, if $x=2$ and $y=4$, we want $lcm(2,4)=4$.

So let’s try one more example:

How many integers are there in the range $[10,30]$ that are divisible by $6$ or $10$? To test it out, let’s also list this manually. The integers we want are: $10,12,18,20,24,30$.

So letting set $A$ be the integers in that range that are divisible by $6$, and letting $B$ be the integers in that range that are divisible by $10$, the lowest common multiple of $6$ and $10$ is not $60$, but $30$. So set $A\cap B$ contains numbers in that range divisible by $30$.

So finally:

$$\begin{array}{rl}|A|+|B|-|A\cap B|& =\left(\lfloor \frac{30}{6}\rfloor -\lfloor \frac{10-1}{6}\rfloor \right)+\left(\lfloor \frac{30}{10}\rfloor -\lfloor \frac{10-1}{10}\rfloor \right)-\left(\lfloor \frac{30}{30}\rfloor -\lfloor \frac{10-1}{30}\rfloor \right)\\ & =(5-1)+(3-0)-(1-0)\\ & =4+3-1\\ & =6\end{array}$$

Extending This to 3 Sets

We can actually extend this idea for $3$ sets (actually it also works beyond $3$, but the formula starts being quite unwieldy).

For $3$ sets $A,B,C$, it holds that:

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|B\cap C|+|A\cap B\cap C|$$

Why is this true? Let’s look at the following Venn diagram.

Notice that if we have $|A|+|B|+|C|$, we would have double counted the elements in $|A\cap B|,|B\cap C|,|B\cap C|$, and triple counted the elements in $|A\cap B\cap C|$.

So consider $|A|+|B|+|C|-|A\cap B|-|B\cap C|-|B\cap C|$. We would have removed the double counts, but elements in $A\cap B\cap C$ which were triple counted, are now not counted at all. So we have to add it back in.

At a food popularity contest, there are $3$ options being voted for by people who are surveyed. We want to know how many people in total were surveyed. The $3$ options were: (A) Lor Mee, (B) Nasi Lemak, (C) Chicken Rice. Anyone who is surveyed can vote for any combination of the options, i.e., a person could choose to vote for all $3$, or any of the $2$ choices, or any single choice. But they must at least vote for something, i.e., everyone who surveyed voted for at least one option, and at most all $3$. We know the following counts:

1. There were $10$ people voting for option A (they might have also voted for other options).
2. There were $7$ people voting for option B (they might have also voted for other options).
3. There were $9$ people voting for option C (they might have also voted for other options).
4. There were $3$ people voting for only both option A and option B.
5. There were $5$ people voting for only both option A and option C.
6. There were $2$ people voting for only both option B and option C.
7. Only $1$ person voted for exactly all $3$ options.

How many people were surveyed?

$$\begin{array}{rl}|A\cup B\cup C|& =|A|+|B|+|C|-|A\cap B|-|B\cap C|-|B\cap C|+|A\cap B\cap C|\\ & =10+7+9-3-5-2+1=17\end{array}$$

So in total, $17$ people were surveyed.

Permutations and Combinations

Let’s move on and away from sets, and start talking about permutations and combinations. Some of these concepts might already be familiar ground, and we will be using it to build up to some bigger concepts.

Permutations of Distinct Items

Let’s begin with the following question:

Given $n$ distinct items, how many ways are there to order the $n$ items?

Let’s try this with $n=3$. Here are all the possible ways to order them.

There are $6$ ways.

What about in general for $n$ distinct items? How many permutations are there? A permutation of the items, is a way to order them.

We can think of it recursively. Let $P(n)$ be the number of ways to permute $n$ distinct items. If $n=1$, there is only $1$ possible ordering: the item itself.

When $n>1$, how do we count this?

So in particular:

$$P(n)=\{\begin{array}{ll}1,& n=1\\ n\times P(n-1),& n>1\end{array}$$

Doesn’t this look familiar? This is $n!$, or ${\prod }_{i=1}^{n}i$.

Permutations With Duplicates

What happens when the items we need to permute has duplicates? For example, let’s say we want to count how many permutations there are of $aab$?

Notice that the answer is not $3!=6$, but rather $3$. In fact, here are the possible permutations:

1. $aab$
2. $aba$
3. $baa

Let’s say we had $2$ items of type $a$ and $1$ item of type $b$. Then the way we obtain the count is $\frac{3!}{2!}=3$.

What about in general? Here’s an idea, we can first label each duplicate. For example, to count the number of ways to permute $aaab$, we can treat it as $a_1{a}_2{a}_{3}b$ first, permute all of them and notice that for example permutations like: $a_1{a}_{2}b{a}_3$ should be treated the same as $a_2{a}_{1}b{a}_3$.

So, using the Rule of Division, for this example, we can argue that the total number of permutations is $\frac{4!}{3!}$.

So in general, if we had $k$ types of items, and we had $n_i$ many copies of the $i^{th}$ item, then the total number of items is: ${\sum }_{i=1}^k{n}_i=n$. Then the total number of permutations is:

$$\frac{n!}{{\prod }_{i=1}^k((n_i)!)}$$

Here’s an example. How many permutations are there of $aaabb$? There are $3$ copies of $a$ and $2$ copies of $b$. There are $5$ items in total. So the answer is:

$$\frac{5!}{3!\cdot 2!}=\frac{120}{6\cdot 2}=10$$

$k$-Permutations of $n$ Distinct Elements

Now, let’s go back to looking at having $n$ distinct elements, but now we only care about picking $k$ of them. How many ways are there to permute that?

For example, let’s say we had $3$ elements $a$, $b$ and $c$. Then here all the possible ways:

1. $ab$
2. $ba$
3. $ac$
4. $ca$
5. $bc$
6. $cb$

But what about for general values of $n$ and $k$? We can again, think about this recursively. When $k=1$, we are just asking how many ways are there to pick $1$ item out of $n$ items. That happens to just be $n$ itself. On the other hand, for $1<k\le n$, we can think of it as having to find $1$ out of the $n$ items to put into the first slot, then there are $n-1$ items remaining, and among which, we need to pick $k-1$ items to permute.

So the recurrence looks something like this:

$$P(n,k)=\{\begin{array}{ll}n,& k=1\\ n\times P(n-1,k-1),& k>1\end{array}$$

What does this resolve to? If you expanded out the recurrence, you might notice that it looks something like this:

$$\begin{array}{rl}P(n,k)& =n\times P(n-1,k-1)\\ & =n\times (n-1)\times P(n-2,k-2)\\ & =n\times (n-1)\times (n-2)\times P(n-3,k-3)\\ & =n\times (n-1)\times (n-2)\times \cdots \times P(n-(k-1),1)\\ & =n\times (n-1)\times (n-2)\times \cdots \times (n-(k-1))\end{array}$$

Which is basically:

$$\prod _{i=0}^{k-1}(n-i)$$

There is another way we can see this. Imagine we considered all $n!$ possible permutations, and then said “any $2$ permutations are considered the same as long as their first $k$ elements are the same”. If we fixed the first $k$ elements, then there are $(n-k)!$ possible ways to permute the remaining elements. So any permutation has $(n-k)!$ that share the same first $k$ elements. Using the Rule of Division, this means there in total:

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

ways to permute $k$ elements out of $n$ distinct elements.

In fact, you can check that:

$$\prod _{i=0}^{k-1}(n-i)=\frac{n!}{(n-k)!}$$

We write this quantity as $P(n,k)$.

Combinations without duplicates

Let’s move on to another kind of counting that we commonly do: combinations! Let’s say we had $n$ distinct items, and this time, we want to count how many ways there are to choose $k$ items from the $n$ items.

For example, if there are $3$ items, $a$, $b$ and $c$. How many ways are there to choose $2$ items out of these $3$?

1. $a$, $b$
2. $a$, $c$
3. $b$, $c$

Notice, the ordering does not matter. What is the formula this time? Again, there are a few ways to prove this. But perhaps the most straightforward way is to again make use of the Rule of Division.

Let’s compare choosing $2$ items out of $3$ versus permuting $2$ items out of $3$. Previously, in [[#k-permutations-of-n-distinct-elements|$k$-Permutations of $n$ Distinct Elements]], notice that the cases we had were:

1. $ab$
2. $ba$
3. $ac$
4. $ca$
5. $bc$
6. $cb$

For permutations, the ordering matters, whereas if we simply want to choose items, it does not matter. Again, for this example, notice how we are basically saying that $ab$ and $ba$ are the same. Because they have the same elements, and we do not care about their ordering. Since we picked $2$ items, there are $2!$ ways to permute the items. So this is:

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

We write this quantity as $C(n,k)$, or also write it most commonly as $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

Interestingly, we can also show that $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$. This might be “obvious” if you look at the fraction alone. In fact:

$$\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)=\frac{n!}{(n-(n-k))!(n-k)!}=\frac{n!}{n!(n-k)!}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$

But there’s a very nice intuition behind why this is the case. Again, falling back to our trusty example of $n=3$ and $k=2$:

Instead of picking $2$ items out of the $3$ distinct items $a$, $b$ and $c$ to create a set of size $2$, we can think about how to exclude $3-2=1$ items out of the $3$ distinct items to create a set of size $2$.

1. $a$, $b$ (means we picked $c$ to be excluded)
2. $a$, $c$ (means we picked $b$ to be excluded)
3. $b$, $c$ (means we picked $a$ to be excluded)

The special case of choosing/permuting nothing.

One last thing we need to talk about: What is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)$? Or what is $P(0,0)$?

How many ways are there to choose nothing from a set of $n$ elements? How many ways are there to permute nothing? It might be tempting to think the answer is $0$, but it’s actually defined to be $1$.

There is exactly one way to choose nothing from a set of $n$ elements: The empty set!

There is exactly one way to sequence/permute nothing: The empty sequence!

For that reason, $n!$ is defined to be $1$ when $n=0$.

This actually helps make our computations make more sense. For example, we can say that

$$\left(\genfrac{}{}{0ex}{}{n}{n}\right)=\frac{n!}{(n-n)!\cdot n!}=\frac{n!}{0!\cdot n!}=\frac{n!}{1\cdot n!}=1$$

Applying Combinatorics

Now that we’ve covered the basic quantities, let’s see a few applications of the counting methods shown.

Stars and Bars

Let’s say we had $t$ variables $x_1,x_2,\dots ,x_t$, all of which need to be $\ge 0$. How many value assignments can we give each $x_i$, so that:

$$\sum _{i=1}^t{x}_i=n$$

For example, if $n=5$, $t=3$, then there are $36$ ways (far too many for us to list out here). As a simpler example, if $n=5$, and $t=2$, there are $6$ ways.

1. $x_1=0$, $x_2=5$
2. $x_1=1$, $x_2=4$
3. $x_1=2$, $x_2=3$
4. $x_1=3$, $x_2=2$
5. $x_1=4$, $x_2=1$
6. $x_1=5$, $x_2=0$

How should we even count the number of possible ways? Even for small values of $n$ and $t$, the number of cases becomes astronomically large.

The technique is called stars and bars. Here’s the idea, again consider $n=5,t=3$:

Think about how if we had $n+(t-1)$ slots, then we can pick $t-1$ slots to be bars in order to “force” the remaining $n$ slots to be stars. If we do this, then the first grouping of stars before the first bar is the value of $x_1$. The second grouping of stars behind the second bar is the value of $x_2$, and so on. The last grouping of stars after the $(t-1{)}^{th}$ bar is the value of $x_4$.

Notice the sum of the values is exactly the number of stars we have: $n$.

So to find out how many ways to assign values to the $t$ variables, is to just pick $t-1$ bars out of $n+(t-1)$ possible positions. In other words:

$$\left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)$$

Block Walking

Let’s try another one. Given a grid of $6$ columns, and $4$ rows, where we start from the bottom left. And we are only allowed to either take one step up, or one step to the right each time. How many ways are there for us to go from the bottom left to the top right?

In the picture below, the red and blue path are examples of paths you can take.

So here’s the idea, treat the red path as a sequence $(U,U,R,U,R,U,R,R,R,R)$. The blue path is a sequence $(R,R,U,R,R,R,R,U,U,U)$. Notice that for $4$ rows and $6$ columns, we have to take $4$ “up” steps, and $6$ “right” steps. A different sequencing of the “up” and “right” steps gives us a different path.

Again, this is similar as to stars and bars. But this time, we have $4+6$ slots, $4$ of which we need to pick to be “up” steps, and the remaining to be “right” steps.

In general, for $c$ columns and $r$ rows, the number of paths is given as:

$$\left(\genfrac{}{}{0ex}{}{c+r}{r}\right)$$

Counting Subsets

Let’s say we had a set $A$ of $100$ distinct elements.

1. How many subsets are there of size $2$?
2. How many subsets are there of size at most $2$?
3. How many subsets are there of size at least $3$?

Part 1: To answer the first question, this was pretty much just $\left(\genfrac{}{}{0ex}{}{100}{2}\right)$. But what about the other two?

Part 2: Note that there are $\left(\genfrac{}{}{0ex}{}{100}{0}\right)$ many subsets of size $0$, that there are $\left(\genfrac{}{}{0ex}{}{100}{1}\right)$ many subsets of size $1$, and $\left(\genfrac{}{}{0ex}{}{100}{2}\right)$ many subsets of size $2$.

Part 3: As for this part, we could solve it directly, like so:

$$\sum _{i=3}^{100}\left(\genfrac{}{}{0ex}{}{100}{i}\right)$$

Or, perhaps a little more simply: we could notice that there are $2^{100}$ possible subsets of $A$. To count the number of subsets that are $3$ or larger, we can just subtract away the subsets that are up to size $2$ from $2^n$. Which gives us:

$$2^n-\left(\genfrac{}{}{0ex}{}{100}{0}\right)-\left(\genfrac{}{}{0ex}{}{100}{1}\right)-\left(\genfrac{}{}{0ex}{}{100}{2}\right)$$

Turns out, both these quantities are the same!

Counting Permutations

Let’s say there were $4$ people: Alice, Bob, Clara, Dean. Let’s say that we had to arrange then in a line but Bob refuses to stand next to Dean. How many ways are there to arrange them in a line?

One way we could do this would be to count three cases separately, where we make $4$ slots, place Bob and Dean down first separately from each other, and then count how many permutations we could get.

There are $3$ possible cases that we can treat similarly. Pick any of the $2$ non-adjacent slots. There are $2!$ ways to arrange Bob and Dean, and then there are also $2!$ ways to arrange Alice and Clara. So there are $(2!\times 2!+2!\times 2!+2!\times 2!)=12$.

There is an alternative way to count this: What about we count the number of ways where Bob and Dean are arranged together? We first treat them like a pair, attached at the hip. Then we count the number of ways we can arrange everyone so that Bob and Dean are stuck together, then subtract that number away from $4!$.

So if we treat Bob and Dean as being stuck together. Then they’re either arranged as Bob-Dean, or as Dean-Bob. Then for each of these cases (of which there are $2$), there are $3!$ possible ways to permute: Alice, Clara, and the Bob-Dean pair. So in total, there are $2\times 3!=12$ ways to arrange the 4 people, such that Bob and Dean are next to each other. Subtracting this away from $4!=24$ yields us $12$ as our answer.

A Sense of Scale

Let’s see some examples of why combinatorics is useful and helpful.

Binomial Coefficients and Nested For Loops

Let’s say we had some code that looked like this:

total = 0
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			total += arr[i][j][k]	

How many iterations does this for loop make? Notice here that there is an iteration whenever $i<j<k$, and all 3 values are taken from the range $[0,n-1]$. How do we count how many iterations we have done?

One very straightforward way is to literally count based on the possible values:

$$\sum _{i=0}^{n-1}\sum _{j=i+1}^{n-1}\sum _{k=j+1}^{n-1}1=\sum _{i=0}^{n-1}\sum _{j=i+1}^{n-1}(n-j-1)$$

then looking at the inner sum, we notice the values range from $(n-(i+1)-1)=(n-i-2)$ to $n-(n-1)-1=0$. So we can say the following:

$$\sum _{i=0}^{n-1}\sum _{j=i+1}^{n-1}(n-j-1)=\sum _{i=0}^{n-1}\sum _{t=0}^{n-i-2}t$$

Now the inner sum is just summing over an arithmetic progression:

$$\sum _{i=0}^{n-1}\sum _{t=0}^{n-i-2}t=\sum _{i=0}^{n-1}\frac{(n-i-2)(n-i-1)}{2}$$

Since $i$ ranges from $0$ to $n-1$, the fraction ranges from $\frac{(n-2)(n-1)}{2}$ to $0$. So again, by changing variables:

$$\begin{array}{rl}\frac{1}{2}\sum _{i=0}^{n-1}(n-i-2)(n-i-1)& =\frac{1}{2}\sum _{r=1}^n(r-1)(r)\\ & =\frac{1}{2}\sum _{r=1}^n(r^2-r)\\ & =\frac{1}{2}\left(\sum _{r=1}^n{r}^2-\sum _{r=1}^{n}r\right)\\ & =\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}\right)\\ & =\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}-\frac{3n(n+1)}{6}\right)\\ & =\frac{1}{2}\left(\frac{n(n+1)(2n+1)-3n(n+1)}{6}\right)\\ & =\frac{1}{2}\left(\frac{n(n+1)(2n+1-3)}{6}\right)\\ & =\frac{1}{2}\left(\frac{n(n+1)(2n-2)}{6}\right)\\ & =\frac{1}{2}\left(\frac{2n(n+1)(n-1)}{6}\right)\\ & =\frac{n(n+1)(n-1)}{6}\\ & =\frac{n(n^2-1)}{6}\\ & =\frac{n(n-1)(n+1)}{6}\end{array}$$

That was a lot of effort! What if I told you there was a much more straightforward way? We basically just want to count how many distinct triplets $\{i,j,k\}$ we can pick from the set $[0,n-1]$.

This happens to be $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. In fact, we can check this!

$$\left(\genfrac{}{}{0ex}{}{n}{3}\right)=\frac{n!}{(n-3)!\cdot 3!}=\frac{n(n-1)(n-2)}{3\cdot 2\cdot 1}=\frac{n(n-1)(n-2)}{6}$$

Interestingly, this tells us at the program makes $\Theta (n^3)$ iterations.

Some Useful Bounds on Combinatorial Properties

Let us end this unit by getting a sense of scale whenever we are counting. This is particularly useful when we are thinking about “generating all possibilities” or “just trying all possible solutions”.

Often times, having an approximation of the quantities are “good enough” for us to eyeball values. Let’s look at two very common approximations for factorials and binomial coefficients.

Stirling’s Approximation

The first is Stirling’s asymptotic approximation for $n!$. Think of “asymptotic approximation” as meaning “the larger the value of $n$, the more accurate the approximation”.

Stirling’s approximation states that:

$$n!\sim \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$$

This makes the term of the right sometimes a little more useful to deal with.

Bounding Binomial Coefficients

The second is for binomial coefficients. Given any $n$ and $0\le k\le n$

$${\left(\frac{n}{k}\right)}^k\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\le {\left(\frac{n\cdot e}{k}\right)}^k$$

An example application

For example, consider the following problem statement:

Given a list $L$ of $n$ pairs $(s_1,e_1),(s_2,e_2),\dots ,(s_n,e_n)$ such that the $i^{th}$ pair denotes the start and end time of the $i^{th}$ event. We will say two distinct events $i\ne j$ are clashing if ($s_i\le s_j$ and $e_i\le e_j$) or ($s_j\le s_i$ and $e_j\le e_i$). Find out what largest subset $S\subseteq L$ of events we can schedule so that none of the events in $S$ clash with each other.

This is a very classical algorithms problem, while we won’t have the tools to solve it here, let’s at least think about some very “straightforward” solutions.

What about the following strategy?

1. Set a variable $len=0$.
2. Go through all possible subsets $S$ of $L$.
3. For each subset $S$, check whether they contain clashing events. 1. If they do, ignore this subset. 2. If they don’t, update $len=max(len,|S|)$.
4. Return $len$.

This way we do find the largest subset. But how long did it take? What is the relationship between the running time of this strategy versus the number of events?

For a subset of length $\ell \ge 2$, we need to check $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ possible pairings to see if the subset contains any clashing events. There are $\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ many subsets of $L$ of length $\ell$. We need to check all possible subsets where $\ell$ ranges from $1$ to $n$. So in total, we take this many steps:

$$\sum _{\ell =2}^n\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)=\sum _{\ell =1}^n\frac{n!}{(\ell !)(n-\ell )!}\cdot \frac{\ell !}{(\ell -2)!\cdot 2!}=\sum _{\ell =1}^n\frac{n!}{2(n-\ell )!(\ell -2)!}$$

Let’s say we want to lower bound the amount of steps needed minimum. How do we even begin approximating this?

One way would be to lower bound the original summation:

\begin{align*} \sum_{\ell = 2}^n \binom{n}{\ell}\binom{\ell}{2} &\geq \sum_{\ell = 1}^n\left(\frac{n}{\ell}\right)^\ell \left(\frac{\ell}{2}\right)^2 \\ &\geq \left(\frac{n}{\sqrt{n}}\right)^\sqrt{n} \left(\frac{\sqrt{n}}{2}\right)^2 \\ &\geq \left(\sqrt{n}\right)^\sqrt{n} \cdot \frac{n}{4}\\ &\geq n^{\frac{\sqrt{n}}{2}}\\ &\geq 2^{\frac{\sqrt{n}}{2}}\\ \end{align*}

Which is close to being exponential in $n$. This means the strategy scales quite badly when we have more and more events.