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
.
May 26, 2012 at 5:44 pm |
Gower, 6th paragraph, definition of function: (x,y) in F! Bye.
Thanks — corrected now.
May 26, 2012 at 6:08 pm |
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.
May 26, 2012 at 7:01 pm
That’s another way of expressing my motivation for putting in the extra sentence.