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 be a finite set with elements. How many functions are there from to ? How many relations are there on ?
Show that the number of relations on such that, for each , there exists at least one with , is .
Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations for which, in addition, for each , there exists at least one with , is
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 to , then, is a subset of such that for every there is exactly one with . For each we get choices for , and the choices don’t affect each other, so the answer is .
Actually, I didn’t really need the Cartesian-products definition there — all I needed was that for every there is a unique such that , and that any can be chosen. So here is a concise and adequate answer to the question.
For each there are choices for . Hence, there are possible functions .
With relations, however, the Cartesian-products definition indisputably makes things easier. Here’s the answer.
The set has size . It therefore has subsets. Therefore, the number of relations on is .
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 are defined (formally) to be subsets of .
Now we are asked for the number of relations such that for every there is at least one such that . Or rather, we’re given the number, , 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 there is some constraint. Let’s focus on just one . How many ways are there of choosing which are related to that ? 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 s. So the number of ways of choosing which satisfy is the number of non-empty subsets of , which is . Ah, that looks promising. It’s clear that what we choose for one doesn’t affect what we choose for any other , so we get to choose an arbitrary non-empty subset for each , which we can do in ways.
If we used the answer, we would have thought as follows. What is the significance of that ? Well, is the number of subsets of a set of size , so the most natural structure of size is probably the number of non-empty subsets of a set of size . The fact that we raise this to the power suggests that we are choosing independent non-empty sets. Wait, that’s exactly what we’re doing!
Finally, here’s the answer written down.
For each let be the set of such that . The only constraints on the are that each should be a non-empty subset of . Since there are such sets, the number of relations with this property is , as stated.
It wasn’t essential to define those sets , 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 is likely to arise from independent choices of a non-empty subset of a set of size , 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 relations such that for each there exists with . 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 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 for which something goes wrong.
If it isn’t obvious to you that is closely related to intersections and 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. is some arbitrary property that can apply to pairs .
Going back to the question, our focus is now on counting the number of relations such that for every there exists with and such that, in addition, there exists such that for no do we have .
Now the moment we’ve got 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 on to be good if for every there exists with .
Now for the sets, which, as I have just said, are more or less forced on me.
For each , let be the set of all good relations such that there is no with .
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 . So I define to be the set of good relations that go wrong because of . And now I want to work out the size of the union of the , which is complicated because the 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 of the bad sets. So what is the size of ? This is the set of all good relations such that there is no with , no with , and so on. In other words, it is the set of all good relations such that for each the set of all such that is disjoint from the set . The condition that is good tells us that is non-empty, so the number of possibilities for is the number of non-empty subsets of , which is . Aha — now we see where the in the answer comes from, and why we were indeed destined to count the number of non-empty subsets of a set of size .
Since for each the constraints on are the same, and do not affect each other, the total number of good relations such that for every is .
Since the size of depends only on (assuming, as we are, that the are distinct), the sum of these sizes over all -tuples is . Therefore, by the inclusion-exclusion formula, the size of is
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 , the number of good relations. That last number conveniently equals when , so our final answer is
as it should be.
Of course, it wasn’t a coincidence that the number of good relations was the 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 such that blah” then it is extremely likely that you should start by writing “let be the set of all such that blah”, after which your task will be to work out the size of the union of the .
3. To do this, you will use the inclusion-exclusion formula, and typically you will find that calculating the intersection of any of the (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 blah” then you will almost certainly want to say, “Let be the set of all 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 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 of size to a set of size , when .
First, what is “the entire set”? It’s the set of all functions from to . What is a surjection from to ? It is a function such that for every there exists such that . How did that start? It started “for every “. Since that’s the “for every” case, we’d better define to be the set of all functions such that there is no with . And now we’re away. The size of is easy to calculate, since it’s the set of all functions that take values in , of which there are . One application of inclusion-exclusion and one taking of complements later we end up with the answer, which is