1
$\begingroup$

The number of total surjective functions from $X$ to $Y$ is known to be $T = y!\left\{{x \atop y}\right\}$, with $|X|=x, |Y|=y$.

However, I am interested in the number $P$ of partial surjective functions, that is, elements of $X$ do not necessarily map to an element of $Y$.

An approach I was thinking about was that you can map each partial function $f:X \to Y$ to a total function $f': X \to Y \cup \{\epsilon\}$, where $\forall x \in X \setminus \operatorname{dom}(f), f'(x) = \epsilon$. That is, extending the domain of the partial function such that elements undefined through $f$ map to a special element in $f'$.

Using this, we can say: $$P = (y+1)!\left\{{x \atop y+1}\right\} + T.$$

The added $T$ is to count the partial functions that happen to be total. The first term does not count them since $\left\{{x \atop y+1}\right\}$ counts the number of ways to partition a set of $x$ objects into $y+1$ non-empty subsets. Interrestingly enough, by rearranging a bit, we also have:

$$P = y!\left\{{x+1 \atop y+1}\right\}.$$

Is the reasoning correct? Is there a more elegant approach?

$\endgroup$
1
$\begingroup$

Your reasoning is correct. A more elegant approach to prove that formula might be to apply the original proof to partial functions encoded as total functions between pointed sets:

Adjoin an element $\epsilon$ to both $X$ and $Y$. The partial surjective functions $f: X \to Y$ are in one-to-one correspondence to the total surjective functions $f_\epsilon : X\sqcup\{\epsilon\} \to Y\sqcup\{\epsilon\}$ with $f_\epsilon(\epsilon)=\epsilon$. Their number is given by the number of ways to partition $X\sqcup\{\epsilon\}$ into $|Y\sqcup\{\epsilon\}|$ non-empty subsets times the number of ways to permute $Y\sqcup\{\epsilon\}$ such that $\epsilon$ remains fixed. The first factor is given by $\left\{{x+1 \atop y+1}\right\}$ and the second factor is given by $y!$ (with $|X|=x$ and $|Y|=y$).

$\endgroup$

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.