3
$\begingroup$

If $X = \{1, 2, 3\}$ and $Y = \{1, 2, 3, 4, 5, 6\}$, how many injections are there from $X$ to $Y$? How many surjections are there from $Y$ to $X$?

For the injections from $X$ to $Y$ there should be $6$ functions for $1$, $5$ functions for $2$ and $4$ functions for $3$.

So $6*5*4 = 120$ injections from $X$ to $Y$.

But I am a little confused for the second part. How exactly will I be able to find what the total number of functions (both injective and surjective) are? I can't use the same method as before because $|Y|$ is greater than $|X|$. I think I need to find the number of injections and then subtract it from the number of total functions to get the number of surjections. But I am a little confused about how I would apply the principle of inclusion-exclusion here to do that.

Any help?

$\endgroup$
2
$\begingroup$

Let $A_i$ be the event where the element $i \in X$ is not matched. By defining number of functions $Y \to X$ as, say $B$, number of surjections $Y \to X$ is

$$B - |A_1 \cup A_2 \cup A_3|$$

Finding $B$ is easy, indeed we have $B = 3^6 = 729$. In order to find $|A_1 \cup A_2 \cup A_3|$, first notice that we have $|A_1| = |A_2| = |A_3|$ and $|A_1 \cap A_2| = |A_1 \cap A_3| = |A_2 \cap A_3|$ by renaming the elements. And we also have

$|A_1| = 2^6 = 64$

$|A_1 \cap A_2| = 1$

$|A_1 \cap A_2 \cap A_3| = 0$

Now, by Inclusion-Exclusion Principle, we have $$|A_1 \cup A_2 \cup A_3| = |A_1|+|A_2|+|A_3|-|A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3|+|A_1 \cap A_2 \cap A_3|$$ $$=3|A_1|-3|A_1 \cap A_2|+|A_1 \cap A_2 \cap A_3| = 3\cdot64-3\cdot1+0 = 189$$

So number of surjections $Y \to X$ is $729 - 189 = 540$, which is also equal to $S(6,3)\cdot3!$ where $S(6,3)$ is the Stirling Number of the Second Kind and $3!$ comes from the distinguishable elements (It's because Stirling Numbers of the Second Kind is defined for indistinguishable objects but we have three distinguishable elements here in $X$).

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