Showing $|\mathcal{I}_X|=\sum_{r=0}^n{n \choose r}^2r!$.

This is Exercise 5.11.3 of Howie's "Fundamentals of Semigroup Theory".

Definition 1: Let $X$ be a set. The symmetric inverse semigroup, denoted $\mathcal{I}_X$, consists of all partial one-to-one maps of X under composition of relations.

The Question:

If $\lvert X\rvert=n$, show that $$\lvert\mathcal{I}_X\rvert=\sum_{r=0}^n{n \choose r}^2r!.$$

My Attempt:

Let $\alpha$ be a one-to-one partial map on $X$. Let $\lvert \operatorname{im}(\alpha)\rvert=k$. Then there are ${n \choose k}$ possible choices for the elements of $\operatorname{im}(\alpha)$, up to the $k!$ possible permutations of these elements. Summing over $k$ then gives $\lvert\mathcal{I}_X\rvert$, but this is wrong.

I don't understand where the extra factor of ${n\choose k}$ comes from.

Partial means that your domain is not all $X,$ hence you also have to choose the $r$ elements of the domain, hence $\binom{n}{r}.$
• I understand that, but why isn't one ${n\choose r}$ enough? – Shaun May 1 '17 at 16:37
• So ${n\choose r}$ to get the domain, another ${n\choose r}$ to get the image, and then $r!$ to permute the image elements. – Shaun May 1 '17 at 16:40