Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are the number of onto functions from a set $\Bbb A $ containing m elements to a set $\Bbb B$ containing n elements.

I found that if m = 4 and n = 2 the number of onto functions is 14.

But is there a way to generalise this using a formula? If yes, what is this formula and how is it derived?


I referred to this question but my doubt was not cleared: how many one to one and onto function?

If not, Then what is the standard way of doing it?

If you explain this to me with an example please explain with the example of m = 5 and n = 3.

important This is a part of my curriculum and I have an important exam tomorrow. So, I request you to make haste in giving me the solution. I will be very grateful to you.

share|cite|improve this question
up vote 26 down vote accepted

Obviously if $m<n$, there are no function from $\Bbb A$ onto $\Bbb B$, so assume that $m\ge n$. We’ll use an inclusion-exclusion argument. There are $n^m$ functions of all kinds from $\Bbb A$ to $\Bbb B$. If $b\in\Bbb B$, there are $(n-1)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b\}$, i.e., functions whose ranges do not include $b$. We need to subtract these from the original $n^m$, and we need to do it for each of the $n$ members of $\Bbb B$, so a better approximation is $n^m-n(n-1)^m$.

Unfortunately, a function whose range misses two members of $\Bbb B$ gets subtracted twice in that computation, and it should be subtracted only once. Thus, we have to add back in the functions whose ranges miss at least two points of $\Bbb B$. If $b_0,b_1\in\Bbb B$, there are $(n-2)^m$ functions from $\Bbb A$ to $\Bbb B\setminus\{b_0,b_1\}$, and there are $\binom{n}{2}$ pairs of points of $\Bbb B$, so we have to add back in $\binom{n}2(n-2)^m$ to get


which can be expressed more systematically as


Unfortunately, this over-corrects in the other direction, by adding back in too much. The final result, when the entire inclusion-exclusion computation is made, is


which can also be written $$n!{m\brace n}\;,$$ where ${m\brace n}$ is a Stirling number of the second kind. The Stirling number gives the number of ways of dividing up $\Bbb A$ into $n$ non-empty pieces, and the $m!$ then gives the number of ways of assigning those pieces to the $n$ elements of $\Bbb B$.

share|cite|improve this answer
Can you please explain me why the following is a wrong way of approaching the above problem - $\binom{m}n(n!)(n)^(m-n) \$ What I am doing is picking up any n elements from set A and linking it with elements of set B along with permutation of the cases. Now that I have got all the elements of Set B in my range I can distribute the elements left in set A in any order – Dhiraj Barnwal Apr 17 at 6:01
* ${m \choose n} (n!)n^{m-n}$ – Dhiraj Barnwal Apr 17 at 10:26
@Dhiraj: (I was offline yesterday.) The problem is that in general you’re counting functions more than once. For a very simple example, suppose that $A=\{0,1\}$ and $B=\{0\}$, so that $m=2$ and $n=1$. There is clearly only one surjection from $A$ to $B$, but your formula counts it twice. Specifically, it counts it once when you choose $\{0\}$ as your set of $1$ element from $A$, and once again when you choose $\{1\}$ as your set of $1$ element from $A$ — the step represented by $\binom{m}n$ in your calculation. In fact your calculation will always overcount unless $m=n$. – Brian M. Scott Apr 18 at 21:46

The answer is a little complicated. It is $n!S(m,n)$, where $S(m,n)$ is the appropriate Stirling Number of the second kind.

There are nice recursions for the $S(m,n)$, but no simple closed-form formula.

share|cite|improve this answer

Another way to think about this that more naturally shows how this problem maps to Stirling numbers of the second kind comes from Bogart in Introductory Combinatorics. There is an exercise that asks us to come up with a recurrence relation for the number of functions from a set onto another set that has a similar form to the recursive formula for binomial coefficients. To that end, we define a function $f(m,n)$ that is the number of functions from a set of size m onto a set of size n.

Without loss of generality, we take set $\Bbb A $ to be integers {1,...,m}. Now we consider the number of elements in $\Bbb A $ that map to the same element of $\Bbb B$ as m does. The functions in which at least one other element of $\Bbb A $ maps to the same element as m are counted by $nf(m-1,n)$ and the functions in which no other elements of $\Bbb A $ map to the same element as m are counted by $nf(m-1,n-1)$, so we get

$f(m,n) = nf(m-1,n) + nf(m-1,n-1)$

Now, I'm no good at solving recurrence relations, but thanks to Brian we already have a potential formula for $f(m,n)$ so we can substitute it in and see if it checks out:

$f(m,n) = nn!{m-1\brace n} +n(n-1)!{m-1\brace n-1} = n!(n{m-1\brace n} +{m-1\brace n-1})=n!{m\brace n}$

share|cite|improve this answer

one can also get this by the following correspondence:No of onto functions is same as no of ways of distributing m distinct objects into n distinct containers(each container can receive any no. of objects)such that none of the container is left empty

share|cite|improve this answer
1) "No" and "n°" ought to have different notations. See also this for some latex help. $$$$ 2) Is this a hint or is this supposed to immediately yield a solution? If the latter, how? $$$$ – G. Sassatelli May 5 '15 at 11:24

Ans: $n^m - (2^n- 2)$

Solution : Total no. of function is $n^m$, but there are some mappings which are not onto , the total number of such mappings are ${n \choose1} + {n\choose2} + {n\choose3} + \dotsb + {n \choose n-1} = 2^n- 2$

Then the no. of onto function is $n^m - (2^n- 2)$

share|cite|improve this answer
Why ${n \choose 1} + \dotsb$? – jkabrg Jun 9 '15 at 9:34
the total number of not onto mapping is not that number. – Arctic Char Jun 9 '15 at 9:40
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. - From Review – Ben S. Nov 16 '15 at 6:26

protected by Community Jun 9 '15 at 9:10

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.