Counting 'n' objects

CS109 taught me that counting matters. To really appreciate probability and its use cases, one needs to count (the sample space and the event space). Chris Piech, the instructor of the course really dives deep into the intuitions of counting and comes up with some foundational blocks. This blog post would be my way of teaching what I understood. For a more detailed analysis please refer to the course (freely available in YouTube).

Two rules for counting

Step rule of counting

Imagine an experiment with two options, flipping a coin (heads or tails) and rolling a die (six possibilities). If the options don't influence each other (flipping the coin doesn't affect the die), the total number of possibilities for the whole experiment is simply the number of ways we can flip the coin (2) multiplied with the number of ways we can roll the die (6).

In other words, if there are n different things that can happen ( $A_{1}A\_1$, $A_{2}A\_2$, $\dots \backslash dots$, $A_{n}A\_n$), and they don't affect each other, the total number of ways the experiment can go is like multiplying the number of possibilities for each thing (n options multiplied together).

$$\text{number of outcomes}=\mathrm{\mid }{A}_1\mathrm{\mid }\mathrm{\mid }{A}_2\mathrm{\mid }\dots \mathrm{\mid }{A}_n\mathrm{\mid }\backslash text\{number\; of\; outcomes\}\; =\; |A\_\{1\}|\; |A\_\{2\}|\; \backslash dots\; |A\_\{n\}|$$

Let's illustrate this concept further with an example.

We have a 2x2 grid (shown below). What are the number of uniques images that can be formed by filling up the 4 grids?

We assume that each grid can take a combination of Red, Green and, Blue. We also assume that it takes 1 byte (8 bits) of memory to represent a color.

Now that the problem and the assumptions are clear, let's solve this problem step-by-step.

The total number of colors that can be represented by 8 bits

There are 8 steps -- each with 2 outcomes (0 or 1). Each outcome is independent of the other, hence we can use the Step rule of counting here. The total number of colors would be $2^{8}2^8$

Total number of color combination in 1 pixel

Now that we have $2^{8}2^8$ ways to represent a single color, there are 3 colors which can be combined to come with a distinct color in one pixel.

This can be contered with the step rule of counting again. $2^8\times 2^8\times 2^8=2^{24}2^8\; \backslash times\; 2^8\; \backslash times\; 2^8\; =\; 2^\{24\}$

Total number of unique images

You can possible guess what I am going to do.

$$2^{24}\times 2^{24}\times 2^{24}\times 2^{24}2^\{24\}\; \backslash times\; 2^\{24\}\; \backslash times\; 2^\{24\}\; \backslash times\; 2^\{24\}$$

OR rule of counting

This one is simple. If you have n sets of outcomes and you want to know all the possible outcomes from either of the sets, you would have to add the number of outcomes from all the sets.

Imagine you're at a vending machine, and you can either:

Choose a cold drink: 5 options (Coke, Sprite, Fanta, Orange Juice, Water)

OR

Choose a hot drink: 3 options (Coffee, Tea, Hot Chocolate)

How many total choices do you have?

With the OR rule, we simply add the possibilities:

Total choices = Cold drink options + Hot drink options

Total choices = 5 + 3 = 8

We have covered the foundations of counting. In the following sections, we build some abstractions on top of them. Specifically, we delve into different ways of counting when we are given $nn$ objects.

Count the arrangements (Permutations)

Given $nn$ distinct objects, how many ways can we arrange them?

Let's consider a set of alphabets {a, b, c, d} and 4 positions each of which can take an alphabet.

We can solve this problem with our friendly step rule of counting. There are 4 choices for the 1st position, once chosen, there are 3 choices for the 2nd position and so on.

Applying the step rule of counting, the total number of arrangements are $$4\times 3\times 2\times 1=4!4\; \backslash times\; 3\; \backslash times\; 2\; \backslash times\; 1\; =\; 4!$$

Given $nn$ indistinct objects, how many ways can we arrange them?

Modifying the previous example we now have the following collection of alphabets [a, a, b, c]. Notice we still have 4 positions to fill but all the alphabets are not distinct.

A 🔑 insight shared by Chris Piech was to consider all the elements distinct and then proceed.

With this modification we now know that there are 4! ways to arrange the alphabets. In reality we have overcounted. Now, we just need to remove the number of times we have overcounted.

Before removing the number of overcounts let's frame this thought a little better. There is either a static number of times we can overcount (which needs to be subtracted) OR there is a multiplicative factor by which we can overcount (which needs to be divided). In this case we have overcounted in multiples.

Consider a, a, b, c as an arrangement. Here there are 2 ways we can place the 'a's (if they were distinct).

Both the arrangements are different if we consider two distinct 'a's, but that is not the case here. Continuing this thought we understand that for all the distinct arrangements with a, b, and c there are 2 duplicates (the 'a's swapping places).

This means that we would need to divide the 4! (all distinct) by 2 (two 'a's) and we get our desired answer $\frac{4!}{2!}\backslash frac\{4!\}\{2!\}$.

What if we have the following alphabets [a, a, a, c] and the same 4 positions. The number of times we overcount is actually the number of arrangements of 'a's if they were distinct (which is 3!). Hence the total number of ways we can arrange the alphabets are $\frac{4!}{3!}\backslash frac\{4!\}\{3!\}$

We can formulate it all by stating that if we have $nn$ objects and out of them $n_1,n_2,\dots n_{r}n\_\{1\},\; n\_\{2\},\; \backslash dots\; n\_\{r\}$ are indistinct, the total number of arrangements would be: $$\frac{n!}{n_1!n_2!\dots n_r!}\backslash frac\{n!\}\{n\_\{1\}!\; n\_\{2\}!\; \backslash dots\; n\_\{r\}!\}$$

Count the ways to choose k objects (Combinations)

Given $nn$ distinct objects, in how many ways can we choose $kk$ objects from them?

You have thrown a birthday party for $nn$ people, but you have miscalculated and can only choose k people (k < n) to have cake. How many ways could you do that?

If you are thinking step-by-step you are on the right track.

1. The first part of the problem is to line the n distinct people. We can do that in n! ways.
2. The next part is to draw a partition between the first k people. We can do that only 1 way.
3. We do not care about the arrangements of the first k people. There are a total of k! arrangements.
4. We do not care about the arrangements of the rest of the (n-k) people. There are a total of (n-k)! arrangements.

$$\text{number of ways to choose k from n objects}=n!\times 1\times \frac{1}{k!}\times \frac{1}{(n-k)!}=\frac{n!}{k!(n-k)!}\backslash text\{number\; of\; ways\; to\; choose\; k\; from\; n\; objects\}\; =\; n!\; \backslash times\; 1\; \backslash times\; \backslash frac\{1\}\{k!\}\; \backslash times\; \backslash frac\{1\}\{(n-k)!\}\; =\; \backslash frac\{n!\}\{k!(n-k)!\}$$

❤️ I really like this problem, because this was the first time I derived the equation of combination, that too with counting.

Note: Choosing k objects from n distinct objects is also denoted as $C_r^{n}C\_\{r\}^\{n\}$

Given $nn$ indistinct objects, in how many ways can we choose $kk$ objects from them?

This is quite easy, there is only 1 way in which you can choose k objects from n indistinct objects.

Count the ways of putting objects in r buckets

Given $nn$ distinct objects, in how many ways can we put them in $rr$ buckets?

We have 3 distinct shapes that we need to put in 3 buckets. This problem is the same as arranging the 3 distinct shapes in 3 positions but where duplication is allowed.

This means that there are 3 ways for the first bucket, 3 ways for the second, and 3 ways for the third. With the step rule of counting, there are $3^{3}3^3$ ways in total.

Formulating the concept, if there are n distinct objects and r buckets, there are $n^{r}n^r$ ways to bucket.

Given $nn$ indistinct objects, in how many ways can we put them in $rr$ buckets?

Now we have n indistinct objects that we need to put in r buckets. The idea here is to add (r-1) dividers to the mix. Let's consider 3 objects and 2 buckets, the diagram below shows the objects and the dividers.

Simply counting the number of arrangements would give us the desired result.

This now becomes a problem of arranging indistinct objects. We can formulate this as $$\frac{(n+r-1)!}{n!(r+1)!}\backslash frac\{(n+r-1)!\}\{n!(r+1)!\}$$

Summary

Thank you for your time. I hope I could do some justice to the topic on counting. I have been floored with the way the intuitions were hidden all this time. Happy learning.

Acknowledgement

I would like to thank Udbhas Mitra, Sayak Paul for their review on the blog post.