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?
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$).