A look at a few Tripos questions IX

Exam day approaches, so I’ve decided to prioritize. Instead of doing question 7C, which isn’t all that interesting (in the sense that it doesn’t give me much scope to emphasize principles of more general use in exams), I’m going to skip it, and instead, if I get time, go through a groups question or two. But first I will do the final Numbers and Sets question because it involves something a lot of people dislike: the inclusion-exclusion principle. It’s worth getting comfortable with this, because it comes up year after year (either in Numbers and Sets or in Probability). You may think that applying the principle requires some ingenuity. The aim of this post is to convince you that it can be done on autopilot.

8C. Let $X$ be a finite set with $n$ elements. How many functions are there from $X$ to $X$ ? How many relations are there on $X$ ?

Show that the number of relations $R$ on $X$ such that, for each $y\in X$ , there exists at least one $x\in X$ with $xRy$ , is $(2^n-1)^n$ .

Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations $R$ for which, in addition, for each $x\in X$ , there exists at least one $y\in X$ with $xRy$ , is

$\displaystyle \sum_{k=0}^n(-1)^k\binom nk(2^{n-k}-1)^n$ .

In my posts from last autumn, I went to great lengths to stress that the formal definitions of “function” and “relation” (as subsets of Cartesian products) should not be thought of as what those concepts are really about. I’m not going to revisit those arguments here, but just make the point that if you’re ever asked a question about numbers of functions and relations, then you obviously need to be completely clear about what constitutes a function/relation and when two of them are distinct. Here the formal definitions are absolutely necessary, and much easier to use than any more intuitive concept you might have.

A function from $X$ to $X$ , then, is a subset $F$ of $X\times X$ such that for every $x$ there is exactly one $y$ with $(x,y)\in F$ . For each $x$ we get $n$ choices for $y$ , and the choices don’t affect each other, so the answer is $n^n$ .

Actually, I didn’t really need the Cartesian-products definition there — all I needed was that for every $x$ there is a unique $y$ such that $y=f(x)$ , and that any $y$ can be chosen. So here is a concise and adequate answer to the question.

For each $x\in X$ there are $n$ choices for $f(x)$ . Hence, there are $n^n$ possible functions $f:X\to X$ .

With relations, however, the Cartesian-products definition indisputably makes things easier. Here’s the answer.

The set $X\times X$ has size $n^2$ . It therefore has $2^{n^2}$ subsets. Therefore, the number of relations on $X$ is $2^{n^2}$ .

One could argue that the last sentence there is unnecessary, but I put it there just to make absolutely clear that I know that relations on $X$ are defined (formally) to be subsets of $X\times X$ .

Now we are asked for the number of relations such that for every $y\in X$ there is at least one $x\in X$ such that $xRy$ . Or rather, we’re given the number, $(2^n-1)^n$ , and asked to justify it.

That potentially makes things easier, since it gives us two options. We could simply try to work out the number and then check at the end that what we get agrees with the answer given. But we could also try to use the answer as a clue to the derivation of the answer.

The first approach (to trying to solve the question) would be something like this. We see that for each $y$ there is some constraint. Let’s focus on just one $y$ . How many ways are there of choosing which $x$ are related to that $y$ ? Well, there must be at least one, but other than that there aren’t any constraints. In other words, we can choose any non-empty set of $x$ s. So the number of ways of choosing which $x$ satisfy $xRy$ is the number of non-empty subsets of $X$ , which is $2^n-1$ . Ah, that looks promising. It’s clear that what we choose for one $y$ doesn’t affect what we choose for any other $y$ , so we get to choose an arbitrary non-empty subset for each $y$ , which we can do in $(2^n-1)^n$ ways.

If we used the answer, we would have thought as follows. What is the significance of that $2^n-1$ ? Well, $2^n$ is the number of subsets of a set of size $n$ , so the most natural structure of size $2^n-1$ is probably the number of non-empty subsets of a set of size $n$ . The fact that we raise this to the power $n$ suggests that we are choosing $n$ independent non-empty sets. Wait, that’s exactly what we’re doing!

Finally, here’s the answer written down.

For each $y\in X$ let $R_y$ be the set of $x$ such that $xRy$ . The only constraints on the $R_y$ are that each should be a non-empty subset of $X$ . Since there are $2^n-1$ such sets, the number of relations $R$ with this property is $(2^n-1)^n$ , as stated.

It wasn’t essential to define those sets $R_y$ , but on the spur of the moment I felt like it, and I think it did make the answer slightly easier to write down.

Finally, we get to the interesting part of the question. Again there are two approaches to what we do with the answer we are given: use it as a check at the end, or use it to help us work out how the proof goes. It often happens with applications of the inclusion-exclusion formula that it is hard to see how the expression in front of you relates to the thing you are trying to count. Because of that, I would normally recommend going for the first approach in such questions. For instance, here I can see that $(2^{n-k}-1)^n$ is likely to arise from $n$ independent choices of a non-empty subset of a set of size $n-k$ , but I don’t quite see where those choices are going to come in.

Another piece of advice with inclusion-exclusion applications is this. If you can’t immediately see which union of sets you should be applying the result to (or intersection of complements of sets), then just try to solve the problem without the inclusion-exclusion formula until it becomes clear what the sets should be. Later, I shall explain how to recognise them when they appear.

OK, we’ve got $(2^n-1)^n$ relations $R$ such that for each $y\in Y$ there exists $x\in X$ with $xRy$ . How on earth can we count the ones that have the same property the other way round? At first it looks impossible. However, it looks potentially slightly easier to count the ones that don’t work.

This is another piece of general inclusion-exclusion advice: when you are asked to count something, consider counting its complement. If you want to be really systematic about this, you can actually decide in advance whether the original set or its complement is likely to be a union of sets. Here, for example, we want the relations to satisfy that for every $x$ something happens. So that’s an intersection. Since the inclusion-exclusion formula applies to unions, we should look at the complement, so that now we are looking at those relations such that there exists some $x$ for which something goes wrong.

If it isn’t obvious to you that $\forall$ is closely related to intersections and $\exists$ to unions, then I recommend staring at the following four definitions until you are happy that the first two are the same and the third and fourth are the same. $P$ is some arbitrary property that can apply to pairs $(x,y)\in X\times Y$ .

$\{x\in X:\exists y\in Y\ s.t.\ P(x,y)\}$

$\bigcup_{y\in Y}\{x\in X: P(x,y)\}$

$\{x\in X:\forall y\in Y\ P(x,y)\}$

$\bigcap_{y\in Y}\{x\in X: P(x,y)\}$

Going back to the question, our focus is now on counting the number of relations $R$ such that for every $y\in X$ there exists $x\in X$ with $xRy$ and such that, in addition, there exists $x\in X$ such that for no $y\in Y$ do we have $xRy$ .

Now the moment we’ve got $\exists x\in X$ we have a union, and by this time it’s a safe bet that it’s the union we’re supposed to count. So let us define some sets. But first, I’m getting sick of stating over and over again the property that the relations are already supposed to satisfy, so let’s start with a convenient definition.

Let us define a relation $R$ on $X$ to be good if for every $y\in X$ there exists $x\in X$ with $xRy$ .

Now for the sets, which, as I have just said, are more or less forced on me.

For each $x\in X$ , let $A_x$ be the set of all good relations $R$ such that there is no $y\in X$ with $xRy$ .

The rough thought in the back of my mind is this. Amongst the good relations, there are some that go wrong. Each one that goes wrong goes wrong because of some $x\in X$ . So I define $A_x$ to be the set of good relations that go wrong because of $x$ . And now I want to work out the size of the union of the $A_x$ , which is complicated because the $A_x$ can overlap. But that’s where the inclusion-exclusion formula will come in.

Once we’ve got the sets to which the formula will apply, we’ve broken the back of the question, so I’ll say less about the rest. The main thing we need to know in order to apply the formula is the size of the intersection of $k$ of the bad sets. So what is the size of $A_{x_1}\cap\dots\cap A_{x_k}$ ? This is the set of all good relations $R$ such that there is no $y$ with $x_1Ry$ , no $y$ with $x_2Ry$ , and so on. In other words, it is the set of all good relations $R$ such that for each $y$ the set $R_y$ of all $x$ such that $xRy$ is disjoint from the set $\{x_1,\dots,x_k\}$ . The condition that $R$ is good tells us that $R_y$ is non-empty, so the number of possibilities for $R_y$ is the number of non-empty subsets of $X\setminus\{x_1,\dots,x_k\}$ , which is $2^{n-k}-1$ . Aha — now we see where the $2^{n-k}-1$ in the answer comes from, and why we were indeed destined to count the number of non-empty subsets of a set of size $n-k$ .

Since for each $y$ the constraints on $R_y$ are the same, and do not affect each other, the total number of good relations such that $R_y\cap\{x_1,\dots,x_k\}=\emptyset$ for every $y\in X$ is $(2^{n-k}-1)^n$ .

Since the size of $A_{x_1}\cap\dots\cap A_{x_k}$ depends only on $k$ (assuming, as we are, that the $x_i$ are distinct), the sum of these sizes over all $k$ -tuples is $\binom nk (2^{n-k}-1)^n$ . Therefore, by the inclusion-exclusion formula, the size of $\bigcup_{x\in X}A_x$ is

$\displaystyle \sum_{k=1}^n(-1)^{k-1}\binom nk (2^{n-k}-1)^n$ .

Finally, since what we are actually interested in is the good relations that do not belong to this set, we must subtract this answer from $(2^n-1)^n$ , the number of good relations. That last number conveniently equals $\binom nk (2^{n-k}-1)^n$ when $k=0$ , so our final answer is

$\displaystyle \sum_{k=0}^n(-1)^k\binom nk(2^{n-k}-1)^n$

as it should be.

Of course, it wasn’t a coincidence that the number of good relations was the $k=0$ term, and we could have done this problem by using the intersection-of-complements formulation of the inclusion-exclusion formula. But I myself feel more comfortable with the unions version, even when it requires me to take an extra little step at the end.

I won’t bother to write out a proper answer, since I think it can be extracted quite easily from the account above. But let me repeat some of the key points.

1. If you are asked to apply the inclusion-exclusion formula, then don’t try too hard to relate the problem to the answer you are presented with — if you can, then great, but if you can’t, it is not cause for panic.

2. Describe carefully the object you are trying to count. Typically, your description will involve either “for every” or “there exists” at some point. If it involves “there exists $x$ such that blah” then it is extremely likely that you should start by writing “let $A_x$ be the set of all $x$ such that blah”, after which your task will be to work out the size of the union of the $A_x$ .

3. To do this, you will use the inclusion-exclusion formula, and typically you will find that calculating the intersection of any $k$ of the $A_x$ (the input you have to provide before using the formula) is easy.

4. If the set you are counting involves not “there exists” but “for every”, then you will almost certainly want to look at the complement of that set instead (at least if you want to apply the inclusion-exclusion formula in its unions version). That will convert “for every” into “there exists”. More precisely, if the set you are counting can be described naturally as “the set such that for every $x$ blah” then you will almost certainly want to say, “Let $A_x$ be the set of all $x$ such that not blah”. Now continue as in the “there exists” case, except that this time when you have calculated the size of the union of the $A_x$ you will need to subtract that from the size of the entire set.

Let me quickly illustrate this with another example, which is a very standard application of the inclusion-exclusion formula: calculating the number of surjections from a set $X$ of size $n$ to a set $Y$ of size $m$ , when $m\leq n$ .

First, what is “the entire set”? It’s the set of all functions from $X$ to $Y$ . What is a surjection from $X$ to $Y$ ? It is a function $f$ such that for every $y\in Y$ there exists $x\in X$ such that $f(x)=y$ . How did that start? It started “for every $y\in Y$ “. Since that’s the “for every” case, we’d better define $A_y$ to be the set of all functions $f$ such that there is no $x$ with $f(x)=y$ . And now we’re away. The size of $A_{y_1}\cap\dots\cap A_{y_k}$ is easy to calculate, since it’s the set of all functions that take values in $Y\setminus\{y_1,\dots,y_k\}$ , of which there are $(m-k)^n$ . One application of inclusion-exclusion and one taking of complements later we end up with the answer, which is

$\sum_{k=0}^m(-1)^k\binom mk(m-k)^n$ .

This entry was posted on May 26, 2012 at 2:29 pm and is filed under Cambridge teaching, IA Numbers and Sets. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “A look at a few Tripos questions IX”

Alexis Says:
May 26, 2012 at 5:44 pm | Reply
Gower, 6th paragraph, definition of function: (x,y) in F! Bye.

Thanks — corrected now.
Greg Martin Says:
May 26, 2012 at 6:08 pm | Reply
Regarding your proof of the number of relations, you say “One could argue that the last sentence there is unnecessary”. But in my mind (as someone who marks papers), if the question asks about relations, the word “relation” had better appear in the answer somewhere, if the student wants to convince me that they’re not just dumping random facts on the page and hoping.
- gowers Says:
  May 26, 2012 at 7:01 pm
  That’s another way of expressing my motivation for putting in the extra sentence.

Gowers's Weblog