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