Abstract Nonsense

Crushing one theorem at a time

Number of Derangements


Point of post: In this post we will do a simple, but classic counting exercise to figure out how many derangements there are on [n].

Motivation

A derangement of the set [n]=\{1,\cdots,n\} is an element \pi of S_n (click the symbol if you’re unsure what it means) such that \pi(x)\ne x for all x\in[n]. In this post we will prove, in two ways, how many derangements there are of n objects. This is interesting combinatorially as it answers the question “Suppose that a class of students takes a quiz and the teacher collects them. How many ways can the teacher redistribute the quizzes for peer grading, with the obvious proviso that no student get’s his/her own paper?”  So, with this in mind, let’s begin.

Remark: I shall use \text{card } and |\cdot| interchangeably for cardinality throughout this post.

Theorem: Let D_n be the set of derangements of \{1,\cdots,n\}. Then,

\displaystyle \left|D_n\right|=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}

Proof: Clearly we have that

\displaystyle D_n=\bigcap_{j=1}^{n}\left\{f:[n]\to[n]:f(j)\ne j\right\}

and thus

\displaystyle D_n=[n]-\bigcup_{j=1}^{n}A_j

where A_j=\left\{f:[n]\to[n]:f(j)=j\right\}, and thus

\displaystyle \left|D_n\right|=S_n-\left|\bigcup_{j=1}^{n} A_j\right|

Thus, by the inclusion-exclusion principle it follows that

\displaystyle \left|D_n\right|=n!-\sum_{j=1}^{n}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_s\right|

where S_j=\left\{S\subseteq [n]:|S|=j\right\}. Note though that

\displaystyle \bigcap_{s\in S}A_s=\left\{f:[n]\to[n]:f(s)=s\text{ for all }s\in S\right\}

and evidently this is equipotent to S_{n-j} and thus

\displaystyle \left|\bigcap_{s\in S}\left|A_s\right|\right|=(n-j)!

but, this was true for all S\in S_j. Thus,

\displaystyle \left|D_n\right|=n!-\sum_{j=1}^{n}(-1)^{j+1}\sum_{S\in S_j}(n-j)!

but, clearly since \displaystyle \left|S_j\right|={n\choose j} it follows that

\displaystyle \begin{aligned}\left|D_n\right|&=n!-\sum_{j=1}^{n}(-1)^{j+1}{n\choose j}(n-j)!\\ &=n!\left[1+\sum_{j=1}^{n}\frac{(-1)^j}{j!}\right]\\ &= n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}\end{aligned}

as desired. \blacksquare

The second method uses techinques outlined in Herbert Wilf’s Generatingfunctionology

Proof: Let a_n=\left|D_n\right| and let $G(x)$ be the generating function for a_n. Note that evidently the number of f\in S_n with exactly k fixed points is evidently a_{n-k} from where it easily follows that

\displaystyle S_n=\bigcup_{k=0}^{n}D_{n-k}

so that

\displaystyle n!=\sum_{k=0}^{\infty}{n\choose k}a_{n-k}

taking the \text{e.g.f.} (convoluting) of both sides gives that

\displaystyle \frac{1}{1-x}=e^x G(x)

so that

\displaystyle \frac{e^{-x}}{1-x}=G(x)

Thus, recalling that in general if \left[x^n\right]f(x)=f_n then \displaystyle \left[x^n\right]\frac{f(x)}{1-x}=\sum_{j=0}^{n}f_n. And thus,

\displaystyle \frac{a_n}{n!}=\left[x^n\right]\frac{e^{-x}}{1-x}=\sum_{j=0}^{n}\frac{(-1)^j}{j!}

as required. \blacksquare

References:

1. Wilf, Herbert S. Generatingfunctionology. Boston: Academic, 1994. Print.

Advertisements

November 15, 2010 - Posted by | Fun Problems | ,

No comments yet.

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

%d bloggers like this: