No of surjective functions

Question

The number of surjective (onto) functions defined from $A$ to $B$ where |A| = 5, |B| = 4, is _______

Comments

Please also explain how to count Into functions.

---

A nice paper on counting functions.

http://www.imsc.res.in/~vikram/DiscreteMaths/2011/twelvefold.pdf

Answer 1

We have 4 elements in set B and 5 elements in set A and surjection means every element in B must be mapped to. So, this problem reduces to distributing 5 distinct elements (r = 5) among 4 distinct bins (n = 4) such that no bin is empty, which is given by n! S(r, n), where S(r, n) is Stirling's number of 2nd kind. So, here we need S(5, 4).

We have S(r+1, n) = n* S(r, n) + S(r, n-1)

1

1 1

1 3 1 

1 7 6 1

1 15 25 10 1

So, S(5,4) = 10 and 4! = 24 giving, number of surjective functions = 24 * 10 = 240

Ref: See Theorem 9:

http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/notes1/partset.html

Answer 2

if no of elements in $A$ is $m$ and no  elements in $B$ is $n$ then,

0) no. of functions possible from $A \to B$ is                 : $n^m$

1) one-to-one (injective) functions possible    : ${}^nP_m$

2) surjection

if no of elements $|A|=|B|$ then no of onto (surjective) functions are $n!$

if $|A|=n$ and $|B|=m$ and $m>n$ then no of onto functions from $A \to B$ is : $n^m - {}^nC_1 {(n-1)}^m + {}^nC_2 {(n-2)}^m - {}^nC_3 {(n-3)}^m + \dots + {(-1)}^{n-1} {}^nC_{n-1} 1^m$

3) Bijection

if $|A|=|B|$ then bijection possible. here no of bijection possible from $A \to B$ are : $n!$

Comments

Can you please explain these formulas..?

---

|A|=m & |B|= n then the formula stands correct. isnt it so???

Answer 3

You correctly found that there are $4^{5}$ functions from a set with five elements to a set with three elements. However, this counts functions with fewer than three elements in the range. We must exclude those functions. To do so, we can use the Inclusion-Exclusion Principle.

• There are $\binom{4}{1}$ ways of excluding one element in the codomain from the range and $3^{5}$ functions from a set with five elements to the remaining three elements in the codomain.
• There are $\binom{4}{2}$ ways of excluding two elements in the codomain from the range and $2^{5}$ functions from a set with five elements to the remaining element in the codomain.
• There are $\binom{4}{3}$ ways of excluding two elements in the codomain from the range and $1^{5}$ functions from a set with five elements to the remaining element in the codomain.
• There are $\binom{4}{4}$ ways of excluding two elements in the codomain from the range and $0^{5}$ functions from a set with five elements to the remaining element in the codomain.

By the Inclusion-Exclusion Principle, the number of surjective (onto) functions from a set with five elements to a set with four elements is $=4^{5}-\left[\binom{4}{1}\times 3^{5}-\binom{4}{2}\times 2^{5}+\binom{4}{3}\times 1^{5}-\binom{4}{4}\times 0^{5}\right] = 1024-784=240$

Answer 4

We can analyze the question like this....definitely two of the 5 elements of A would be mapped to same element of B. Hence we can select those two elements in 5C2 ways and now consider these two elements to be a single element. So now we have 4 elements in A to be mapped to 4 elements in B. This can be done in 4! ways.

Hence answer should be 5C2*4!

=240