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

Question

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.

Please help :)

Answer 1

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}.$