Archive for May 26th, 2012

A look at a few Tripos questions IX

May 26, 2012

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.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 3 Comments »

Follow

Get every new post delivered to your Inbox.

Join 1,068 other followers