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 xs. 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.

About these ads

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

  1. Alexis Says:

    Gower, 6th paragraph, definition of function: (x,y) in F! Bye.

    Thanks — corrected now.

  2. Greg Martin Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,420 other followers

%d bloggers like this: