# Counting 1:1 and onto functions

I'm faced with the following questions:

1) How many functions are there from a set of size 3 to a set of size 5? How many of them are 1-to-1?

2) How many functions are there from a set of size 10 to a set of size 2? How many of them are onto?

Attempt:
1) To determine the the number of functions, we can set $A = \{a,b,c\} = a$ and $B = \{d, e, f, g, h\} = b$. So the number of functions is $b^a$ or $5^3$. However, this is a large figure for me to do each one by paper and pencil to determine how many are 1:1. Is there any simple way?

2) Same as part 1 but I don't want to write out $2^{10}$ functions to see how many are onto.

• You've asked quite a few questions now, and have received many answers to your questions, but accepted none. That indicates to some users that you aren't finding answers helpful, and may thus make users reluctant to try and help. +1 for showing some work! Commented Apr 15, 2013 at 1:57
• Can you explain why the number of functions is $b^a$? Commented Apr 15, 2013 at 2:25
• @BenMillwood We can derive $b^a$ functions from give finite sets of $A=a$ and $B=b$. So the length of the subset can be $b$ times $a$ repetition-free times. Commented Apr 15, 2013 at 2:28
• You may want to study these cases, and others, of the Twelvefold way Commented Apr 15, 2013 at 12:15

I am making a function $f$ from a set of $3$ elements, say the set $A=\{a,b,c\}$, to a set $B$ of $5$ elements.

I can choose the value of $f(a)$ in $5$ ways. For every way of deciding what $f(a)$ is, there are $5$ ways to decide what $f(b)$ is, for a total of $5^2$ ways of deciding the values of $f(a)$ and $f(b)$. And for every way of doing that, there are $5$ choices for the value of $f(c)$, for a total of $5^3$.

If we want $f$ to be one to one, then for every choice about the value of $f(a)$, we only have $4$ choices for $f(b)$, since we cannot have $f(a)=f(b)$. And once we have chosen $f(a)$ and $f(b)$, there are only $3$ allowed values for $f(c)$. Thus there are $(5)(4)(3)$ one to one functions from $A$ to $B$.

For the second problem, let our $2$-element set $B$ be, say, $\{0,1\}$. There are, by the same argument as before, $2^{10}$ functions from a set $A$ of $10$ elements to the set $B$.

How many of these $2^{10}$ functions are bad (not onto)? Exactly $2$ of them, the function that send everybody to $0$ and the one that sends everybody to $1$.

• So is it the general case for counting onto functions that $b^a-b$? So here we have $2^{10}-2$ onto functions, correct? Commented Apr 15, 2013 at 2:55
• It is more complicated. For example, for $b=3$, we need to subtract the $2^{10}$ functions that avoid $c$, and $2$ other bunches of $2^{10}$. But then we will have subtracted the $3$ functions that take only one value once too often. So the answer for $b=3$ is $3^a-3\cdot 2^a +3$. There is a similar Inclusion/Exclusion formula for general $b$. Commented Apr 15, 2013 at 3:03
• Since $b=2$ here, would we have $2^a-2*2^a+2$? But this does not make sense because we go into negative numbers. Commented Apr 15, 2013 at 3:15
• For $b=2$, it is $2^a-2$. For $b=3$ it is $3^a-\binom{3}{2}2^a+\binom{3}{1}$. For $b=4$ it is $4^a-\binom{4}{3}3^a+\binom{4}{2}2^a -\binom{4}{1}$. It is difficult to describe the general reasoning in comments! Note that the last terms "fit the pattern." Think of $2^a-2$ as $2^a -\binom{2}{1}1^a$. Commented Apr 15, 2013 at 3:24
• So we would keep on using inclusion and exclusion as we go, or as b increase, correct? Commented Apr 15, 2013 at 3:49

For the first problem, consider that a 1-to-1 function $f:X\to Y$ is the same thing as a choice of subset $f(X)\subset Y$ of size $|X|$, together with a way of matching up the elements of $X$ with the elements of $f(X)$. How many ways are there to do each of these things? (Answering the second of these might be easier if you think of $X = \{1,2,\ldots,n\}$.)

For the second problem, I suggest that it is easier to count how many of those functions are not onto.

An alternative way to count functions which are onto: for each element in the codomain, you've got to pick some element of the domain to map to it. These mapping-to elements have got to be all different, so for the first one you've got all of $A$ to choose from, for the second one you've got one fewer choices, and so on.

Once you've got every element in the codomain being the target of something in the domain, the rest of the domain can map wherever it wants.