# Fundamental principles of counting

Let $| X | = 7$ and $| Y | = 10$.

A- How many different one to one functions are there from $X$ to $Y$?

B- How many different functions are not one to one from $X$ to $Y$?

C- How many different one to one functions from $Y$ to $X$?

D- How many different functions are not one to one from $Y$ to $X$?

I have tired doing these but I think I'm doing them wrong I don't know I got. $4$ for $A$, $6$ for $B$, $0$ for $C$ and I don't know about the last one.

• Your answer for $C$ is correct, but my suggestion for $A$, is that any one-one function from $X$ to $Y$ can be treated as an ordered choice of $7$ elements from $Y$ (can you see this?) To find the number of non one-to-one functions, find the total number of functions and subtract. – астон вілла олоф мэллбэрг Mar 22 '17 at 0:06
• For A, you're mapping any element in $X$ to any element in $Y$. Therefore, there will be $7$ elements in $Y$ that will be mapped to. You can take the elements of $Y$ and choose them such that order matters. There are $10P7$ ways to do this. – Kaynex Mar 22 '17 at 0:07
• So 10P7 = 604800 right ? – user413528 Mar 22 '17 at 0:11
• астон вілла олоф мэллбэрг's suggestion for B will also work for D. – Martin Rattigan Mar 22 '17 at 0:18
• Note that many authors use "one to one" function to mean both 1-1 and onto (injective and surjective), which is impossible between two finite sets of different sizes. – hardmath Mar 22 '17 at 0:28

Just follow the definitions. $f: X \rightarrow Y$ $f$ 1-1. There are $10$ elements of $Y$ that the first element of $X$ can be mapped to. The second element must map to a different element so there are $9$ elements the second element can map to. And $8$ the third can map to. So there are $10*9*8*7*6*5*4$ ways to map the 7 elements of $X$ uniquely to the 10 elements of $Y$..
$f: X \rightarrow Y$ and $f$ not nescessarily 1-1. There are $10$ elements of $Y$ the first element of $X$ can be mapped to. The second element does not have to map to a different element so there are $10$ elements the second element can be mapped to. And $10$ the third can be mapped to. So there are $10^7$ ways to map the 7 elements of $X$ to the 10 elemments of $Y$. But if we don't want to count the 1-1 functions we must subtract $10*9*...*5*4$ that are one to one. So $10^7 - 10*9*....*54$ that are not 1-1.