Find Cardinality of the set $X$ defined below I did this question by crude counting. Since $|S|$ was only $4$, counting didn't took much time but there should be a way to do it for bigger sets.
Let $S = \{a, b, c, d\}$ and  $X = \{f : S \to S \mid f\text{ is bijective and }f(x)\ne x\text{ for each }x \in S\}$
Then
$|X| =\text{ ?}$
 A: Bijections from a set to itself that have no fixed points are called derangements.  The question is how many derangements a set has.  Counting these is a standard application of the inclusion-exclusion principle.
See this article.
The bottom line is perhaps surprising: It's the nearest integer to $\dfrac{n!}{e}$.
For example, if $n=5$ then it is the nearest integer to $\dfrac{5!}e = \dfrac{120}e=44.14553\ldots\ {}$.
The argument goes like this: The number of bijections is $n!$.  Subtract from that the total number of bijections with at least one fixed point and that's the answer.  The number of bijections with at least one fixed point is found as follows.
The number of bijections in which $k$th element is fixed is $(n-1)!$.  Add those up over all $n$ members and you have $(n-1)!n=n!$.
But that is an overcount because when you counted the ones with the first element fixed and then added those with the second element fixed, all the one with both the first and second elements fixed got counted twice.  So subtract the number with both of those fixed, which is $(n-2)!$.  Do likewise over all such unordered pairs, of which there are $\dbinom n 2=\dfrac{n(n-1)}{2}$.  So you are subtracting a total of $\dfrac{n(n-1)}2\cdot(n-2)! = \dfrac{n!}2$.
So far our count of those with at least one fixed point is $n!-\dfrac{n!}2$.
But now you've subtracted too many since you subtracted those with the first and second elements fixed, and those with the first and third elements fixed, and those with the second and third elements fixed.  Those with all three elements fixed got added in three times, then subtracted three times, so they need to get added again.  There are $(n-3)!$ of those.  Do likewise with all sets of three, of which there are $\dfrac{n(n-1)(n-2)}{6}$.  So we get $(n-3!)\dfrac{n(n-1)(n-2)}{6}=\dfrac{n!}6$.
So far our count of those with at least one fixed point is $n!-\dfrac{n!}2+\dfrac{n!}6$.
But now those with four fixed points have been counted too many times, so have have to subtract them, getting $n!-\dfrac{n!}2+\dfrac{n!}6-\dfrac{n!}{24}$.
And so on, up to $n$:
$$
n!-\frac{n!}2+\frac{n!}6-\frac{n!}{24} + \frac{n!}{120} - \cdots \pm \dfrac{n!}{n!}.
$$
This is what we need to subtract from $n!$, the whole number of bijections, getting
$$
n! - n!+\frac{n!}2-\frac{n!}6+\frac{n!}{24} - \frac{n!}{120} + \cdots \pm \dfrac{n!}{n!}.
$$
This is
$$
n!\left( \frac1{0!} - \frac1{1!} + \frac1{2!} - \frac1{3!} + \frac1{4!} - \cdots \pm \frac1{n!} \right).
$$
In other words it's $n!$ times the value at $x=-1$ of the standard power series
$$
e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} +\cdots
$$
except that the series terminates after the $n$th-degree term.
A: I'll derive the inclusion-exclusion argument as an alternative. There are $n!$ permutations. We subtract out the number of permutations in which $f(x) = x$ for one point $x$. We fix one point and permute the remaining $n-1$ points in $(n-1)!$ ways. As there are $n$ such ways to fix one point, we subtract out $n!$. 
However, we have over counted and have to add back in the points in which two points are fixed. We pick our two points in $\binom{n}{2}$ ways. There are then $(n-2)!$ ways to arrange the remaining $n-2$ points. So by rule of product, we multiply to get $\binom{n}{2} \cdot (n-2)! = \frac{n}{2!} = P(n, 2)$, where $P$ is the permutation count function.
We continue this argument to get the formula:
$$D_{n} = n! \cdot \sum_{i=0}^{\infty} \frac{(-1)^{i}}{i!}$$
A: there is also a derivation using exponential generating functions. an arbitrary permutation of a set is made up of a trivial map on the subset of its fixed points, and a derangement on the complement of the fixed set.
the trivial map has only one representative for each cardinality, so its e.g.f. is $e^z$
the number of permutations of a set has the e.g.f. $\sum \frac{n!}{n!}z^n=(1-z)^{-1}$
if $D(z)$ is the e.g.f. for the number of derangements then:
$$
(1-z)^{-1}=D(z)e^z
$$
i.e.
$$
D(z)=\frac{e^{-z}}{1-z}
$$
as series we have
$$
D(z)=\sum_{j=0}^{\infty}\frac{d_n}{n!} =\sum_{j=0}^{\infty}\frac{(-1)^j}{j!}z^j\sum_{k=0}^{\infty}z^k \\
=\sum_{n=0}^{\infty}\sum_{j+k=n}\frac{(-1)^j}{j!}z^n
$$
which gives the number of derangements of $n$ objects as:
$$
d_n = n!\sum_{j=0}^n \frac{(-1)^j}{j!}
$$
A: You have to count the number of permutations with one or more fixed points.If $\lvert S\rvert=n$, set $X_i$ to be the permutations that have $i$ as a fixed point. We have $\lvert X_i\rvert=(n-1)!$ 
Count the number of permutations in $\bigcup\limits_{i=1}^nX_i$ with the inclusion-exclusion formula.
