2
$\begingroup$

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 :)

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I understand that, but why isn't one ${n\choose r}$ enough? $\endgroup$ – Shaun May 1 '17 at 16:37
  • 2
    $\begingroup$ Oh, elements of the domain - sorry! - yes, I understand now. Thank you. $\endgroup$ – Shaun May 1 '17 at 16:38
  • $\begingroup$ Because you need to choose the domain and the image. Two of them. They can be different and you have still bijections. $\endgroup$ – Phicar May 1 '17 at 16:38
  • 2
    $\begingroup$ So ${n\choose r}$ to get the domain, another ${n\choose r}$ to get the image, and then $r!$ to permute the image elements. $\endgroup$ – Shaun May 1 '17 at 16:40
  • $\begingroup$ @Shaun Yes sir. $\endgroup$ – Phicar May 1 '17 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.