Calculate the number of SDR's in $A_i:=\{1,\dots,n\}\setminus\{i\}$ Suppose that $A_1,A_2,\dots,A_n$ are sets, which we refer to as a set system. A (complete) system of distinct representatives is a set $\{x_1,x_2,\ldots,x_n\}$ such that $x_i \in A_i$ for all $i$, and no two of the $x_i$ are the same.
Now, Calculate the number of SDR's in $A_i:=\{1,\dots,n\}\setminus\{i\}$  
Note : This question may be related to Hall's theorem.But i don't know how to calculate the number of SDR's. i just know that they exist.
 A: You can think of each SDR as a bijection $s:[n]\to[n]$ that satisfies the condition that $s(k)\ne k$ for each $k\in[n]$; this is precisely what is meant by the term derangement in bof’s hint and Wikipedia reference. This is a rather difficult question, since there is no nice closed form in terms of $n$ for the number of such bijections. There are a couple of nice recurrences, and there is a fairly nice summation formula that can be derived from the inclusion-exclusion principle, but if you’ve not done much combinatorics, I suspect that it will be pretty hard to come up with the summation formula. Since the formula is given in the Wikipedia article on derangements, I’ll show you how it can be derived.
For the summation formula, let $B_k$ be the set of bijections $s:[n]\to[n]$ such that $s(k)=k$, the ones that are ‘bad’ at $k$. There are $n!$ bijections from $[n]$ to $[n]$ altogether, and we want to remove from this collection those belonging to $\bigcup_{k=1}^nB_k$, so we want to know $\left|\bigcup_{k=1}^nB_k\right|$. 
Suppose that $\varnothing\ne I\subseteq[n]$. A bijection $s$ on $[n]$ belongs to $\bigcap_{k\in I}B_k$ precisely when $s\upharpoonright I$ is the identity on $I$, and $s\upharpoonright\left([n]\setminus I\right)$ is a permutation of $[n]\setminus I$. There are $\left(n-|I|\right)!$ permutations of $[n]\setminus I$, so
$$\left|\bigcap_{k\in I}B_k\right|=\left(n-|I|\right)!\;.$$
From the inclusion-exclusion principle we now have 
$$\begin{align*}
\left|\bigcup_{k=1}^nB_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}B_k\right|\\
&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left(n-|I|\right)!\\
&=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)!\;,
\end{align*}$$
since there are $\binom{n}k$ subsets of $[n]$ of cardinality $k$, and hence
$$\begin{align*}
n!-\left|\bigcup_{k=1}^nB_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}B_k\right|\\
&=n!+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)!\\
&=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)!\\
&=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\;,
\end{align*}$$
which is very close to $\frac{n!}e$ even for quite small $n$.
