# Discrete Mathematics Vignettes: Counting

This spring semester I am co-teaching a first-year undergraduate course in computer science at Rice University. The name of the course is COMP 182: Algorithmic Thinking. In reality the name of the course can be somewhat misleading, as I would rather title it “Introduction to Discrete Mathematics and Algorithm Design and Analysis”, but it doesn’t quite roll off the tongue as easily. However, this is not a post about the course or teaching experience, this is a post about one of the upcoming topics in the class: counting.

## Introduction

What is counting? In general in discrete mathematics counting concerns deriving mathematical expressions which capture the total number of certain objects that exist. Of course, since we can always make an identical copy of an object and thus increase the count by one, what we really mean is counting the objects up to an appropriate notion of isomorphism, or put plainly, counting distinct objects up to whatever notion of being distinct we choose.

While deriving expressions that capture the counts of objects is an important task, what I want to talk about today goes one step beyond the basics of counting, and is rather aimed to provide you with some applied tools you can sue in the future (of course, in the spirit of Alexander Razborov, here by applied I mean applied to the study of mathematics). However, in order to make this primer relatively complete we will start with some basic results in counting, and then switch to the applications of counting techniques and ideas to more interesting problems.

## Permutations

This is the classic problem with which most counting modules of discrete math books start: Find the number of ways in which n distinct objects can be arranged in a line. Key information here is that we are talking about distinct objects and an arrangement in a line. It is easy to show that the total number of such permutations is $n!=1\cdot 2\cdot 3\cdot\ldots\cdot n$. We can do so by observing that given an ordering of n-1 objects we have n places to put the new object in, and this holds for every ordering of n-1 objects. More formally, if we denote the number of permutations of n objects by $P(n)$ then we have $P(n)=nP(n-1)$. Also, while we are here, it is useful to note that there is exactly one way of putting no objects down at all, or in other words $0!=1$.

Now, we can take a look at the number of permutations in a slightly different way. For the sake of brevity we will be denoting the set of n positive integers as $[n]=\{1, 2, 3, ..., n\}$. Consider the set of functions $f:[n]\to[n]$, we will call this set $\mathcal{F}_n=\{f|f:[n]\to[n]\}$. Recall that a function is an assignment of outputs for any given input, such that exactly one output value is assigned to any input value. Thus, we can see that $|\mathcal{F}_n|=n^n$, as for any given input $i\in[n]$ we have n choices of the output value, and since all choices are independent of each other we have a total of $n^n$ functions. A reasonable follow up question, is to ask how many of those functions are bijections. Recall that we call a function a bijection iff for any two distinct input values it produces distinct outputs, and for every possible output value there exists an input value that maps to it via our function. In other words, when we look at $\mathcal{F}_n$ bijections are precisely the functions that assign to each input $i\in[n]$ a distinct output $j\in[n]$ s.t. for any pair of $i_1\neq i_2$ we have $f(i_1)\neq f(i_2)$. Note, that since the functions are from $[n]$ to $[n]$ it follows that such an assignment has to use all possible output values. If we look closer at the structure of such bijection, we can realize that it is essentially a permutation of n distinct objects, since we can think of input values as positions on the line, and outputs as the distinct objects we place in those positions. Hence, it follows that there is $n!$ bijections in $\mathcal{F}_n$.

What we saw above is the fundamental use of counting in combinatorics, we find a combinatorial object of interest (say bijections on the set of n elements) and we count the number of such objects. Often we will see seemingly unrelated families of objects that result in the same total counts, offering us different combinatorial interpretations of the same formula. Furthermore, once we are able to count the number of objects with a given property (say being a bijection) among the total collection of objects (say functions between two sets of n objects) we can immediately get the probability of an object selected uniformly at random to possess the property of interest. In the case of the bijections above we have that $Pr(f\in\mathcal{F}_n,\,f\text{ is a bijection})=\frac{P(n)}{|\mathcal{F}_n|}=\frac{n!}{n^n}$. We will see why such simple observations can be of use a bit later in the post.

## Count once, count twice

Whenever we count number of certain objects we can sometimes derive the formula based on different inputs. This fact becomes useful in cases when we want to show equality between two expressions. In other words, if we want to prove that two expression are equal, one way to do so can be expressing the count of a particular combinatorial object in two ways, each corresponding to one of the expressions. A quick simple example of this proof technique is given by the handshake lemma in graph theory. Consider a simple graph $G=(V, E)$. We want to evaluate the sum of degrees of all vertices $\sum_{v\in V}\mathrm{deg}(v)$. In order to do so, we can think of a counting argument. What is a degree of any given vertex? It is exactly the number of edges incident to that vertex. Hence, if we sum degrees of all the vertices in a graph it follows that we are indirectly counting the edges of the graph. However, each edge in a simple graph is incident to exactly two vertices. This means that when we summed our degrees, we actually counted occurrence of each edge exactly twice (once per endpoint). Thus, it follows that $\sum_{v\in V}\mathrm{deg}(v)=2|E|$. While this result at first might not appear as a counting argument, if you think about it for a bit you can recognize that we essentially counted the number of edges in a graph in two ways, once by considering degrees of vertices and once, by simply counting all edges.

Another common example for double counting comes from the problem of finding the number of subsets of a set with n elements. Specifically, on one hand each subset is determined by whether each element is in or out of it, i.e. for each element in $[n]$ we have two possible choices either it is in the subset (1) or it is not (0), thus the total number of possible subsets is the number of all possible strings of n characters over the alphabet of ${0, 1}$, which is $2^n$. On the other hand, each subset has some size k where $0\leq k\leq n$, and we know that the number of ways to pick k elements from n is $\binom{n}{k}$. Hence, we can conclude that $\sum_{k=0}^n\binom{n}{k}=2^n$.

A fun extension of the argument above can give us a way to count a slightly more complicated set of objects. We are now interested in how many subsets of a set of n elements have an even number of elements in them. On one hand we can express this number as the sum of $\binom{n}{2k}$ with $k\leq n/2$, while on the other hand we can consider the following argument: take an arbitrary subset of a set with n-1 elements, now there is a unique way to extend it to an even sized subset of an n element set. Namely, if our starting subset has an even number of elements, we have to exclude, i.e. assign value 0, to the last element in the n element set, if the starting subset has an odd number of elements then we need to add the last element to it to make the size even, i.e. we assign the value of 1 to the last element. It follows that for any of the $2^{n-1}$ subsets of a n-1 element set, there is a unique extension to an even sized subset of n element set. Hence, we can conclude that $\sum_{k=0}^{n/2}\binom{n}{2k}=2^{n-1}$, or in other words, exactly half of all subsets have an even number of elements in them. This is a nice confirmation to an intuitive guess we might have had originally, but sadly the argument does not extend for the number of subsets with a multiple of 3 elements in them. Let’s formulate this more general version of the question. Let $S(n, k)$ be the number of subsets of a n element set that have size divisible by k. We have from our previous work the values $S(n, 1)=2^n$, and $S(n, 2)=2^{n-1}$. It would be nice if $S(n, 3)$ was simply $2^n/3$, but sadly that is not an integer. However, with a little bit of elbow grease and usage of binomial theorem we can show that $|S(n, 3)-\frac{2^n}{3}|< 1$. I will leave the solution to this problem as an exercise for a curious reader.

To summarize, we just saw how counting the same combinatorial objects from two perspectives can serve us as a proof technique for showing equalities between expressions. Thus, we are starting to explore the field of applications that counting techniques provide us.

## It exists! But I can’t show you an example

Recall how in the bijection counting question we brought up the probability of a randomly picked function from $[n]$ to $[n]$ to be a bijection. Besides the classical uses of probabilities, such as analyses of randomized algorithms, we can also wield probability as a tool for showing existence of objects with desirable properties. This technique is called probabilistic method and it was pioneered in combinatorics by Paul Erdős. The premise for the application is quite simple at the first glance, in order to show that an object $x$ with a desirable property exists, we will show that the probability that a random element $x$ belongs to the set of elements with desirable property $x\in A$, where $x$ is picked from out universe $\Omega$ is greater than 0.

In order to make this more concrete we will work through an application of this method to a graph theoretic question. Consider a complete graph on n vertices $K_n$. We will call a tournament an orientation of the complete graph, i.e. for every edge ${u, v}$ in a complete graph we will pick a direction and replace it with a directed edge $u\to v$ or $v\to u$. It is easy to check that the total number of tournaments on n vertices is $2^{\binom{n}{2}}=2^{\frac{n(n-1)}{2}}$. Now, we are interested in determining whether for $n\geq 3$ there exists a tournament with $n$ vertices that contains at least $(n-1)!/2^n$ Hamiltonian cycles.

To start, consider the sample space of all tournaments on n vertices and assume the uniform distribution on it. Now, we want to introduce a random variable $X$ that counts the number of Hamiltonian circuits (recall that a random variable is a function from the sample space to some set, in our case we have $X:\Omega\to\mathbb{N}$) in a tournament. Fix a node and consider some permutation of the remaining nodes in the tournament (we have a total of $(n-1)!$ such permutations), we want to know when there is a Hamiltonian cycle that achieves that permutation. Clearly we need to have a directed edge from every predecessor to its successor in the cycle, hence in total we need n edges to point in the correct direction determined by our permutation. Now, let’s define an indicator random variable $X_\sigma$ which is equal to 1 whenever the Hamiltonian cycle defined by the permutation $\sigma:[n]\to[n]$ exists in a tournament. We want to compute $Pr(X_\sigma =1)$. In order to do so, we note that we need exactly n edges to have fixed orientation, and hence it follows that the probability of such an event occurring is $1/2^n$ (since we can think of flipping a coin for orientation of each edge, it’s up to reader to check that this process indeed results in uniform distribution over tournaments). Now, by construction we have $X=\sum_{\sigma}X_\sigma$ where $\sigma$ goes over all possible permutations on $n-1$ vertices. Hence, by the linearity of expectation we have that $\mathbb{E}[X]=\sum_{\sigma}\mathbb{E}[X_\sigma]=\sum_{\sigma}Pr(X_\sigma =1)$. Now, using our previous result we can conclude that $\mathbb{E}[X]=(n-1)!/2^n$. Hence, since the expected value is $(n-1)!/2^n$ it follows that there exists some tournament that has at least $(n-1)!/2^n$ Hamiltonian cycles in it.

While it is a stretch to claim that this result is purely enabled by our ability to count combinatorial objects, a lot of key ingredients to the proof rely on our ability to count. Furthermore, this showcases the power of probabilistic method as a non-constructive proof technique for showing existence. In other words, if we can properly count the number of certain objects, we may have a hope of proving interesting results about existence of objects with certain properties.