In the symmetric inverse semigroup, $I_X$, if $|X| = n$, show that $|I_X| = \sum_{r=0}^n \begin{pmatrix} n\\ r\end{pmatrix}^2 r!$

Question

In the symmetric inverse semigroup, $I_X$, if $|X| = n$, show that

$$|I_X| = \sum_{r=0}^n \binom{n}{r}^2 r!$$

This is a question form Howie's book on semigroup theory, unfortunately there isn't a solution to this question and I have no idea how to do it. Any help would be much appreciated.

Answer 1

The partial bijections are partial functions $f:X\longrightarrow X$ such that when you restricted the partial function to the domain, say $X_1\subseteq X$ $f|_{X_1}$ is a bijection. So, by sum principle, you sum over the cardinal of $X_1$ that can be any number from $0$ to $|X|=n$ and you choose the domain and codomain(to choose domain(i.e., $X_1$) you can do it in $\binom{|X|}{|X_1|}$ ways), and then you permute all possibilities.