Counting Functions

Question

Q: The number of surjective functions f from A = { 1 , 2 , 3 , 4 , 5 , 6 } to  B = { 1 , 2 , 3 , 4 , 5 } for which f(6) = 3 is ......?

Answer 1

Number of surjective funtions (onto or co-domain = range) from a set of $m$ elements to a set of $n$ elements is same as putting $m$ distinct balls to $n$ distinct buckets such that no bucket is empty. For $m=6, n= 5$, this is given by $S(6,5)*5! = 15 * 120 = 1800$.

But, here we have an additional constarint that $f(6) =3$ for all the functions. So, our answer must be less than 1800. 

To find this, we can consider 2 cases

1. Let no element map to 3 from $A-\{6\}$, and then add the mapping $(6,3)$.
2. Let all elements from $A-\{6\}$ map to all elements of $B$ and then add the mapping $(6,3)$.

Since in each case we are considering surjective mappings (co-domain = range) we are sure that both these cases are mutually exclusive and for the total cases, simple addition is enough. (In the first case 3 is mapped to by just 6, in in the second case 3 is mapped to by at least two elements including 6).

So, now for 1, it is same as number of surjective functions from a set of 5 elements to a set of 4 elements which is $S(5,4)*4! = 10*24= 240$.

For 2, it is same as the number of surjective functions from a set of 5 elements to a set of 5 elements which is $5! = 120$.

Thus totally we can have $240+120=360$ such surjective functions.

---

$S(m,n)$ is Stirling's number of second kind and is given by the number of ways of partitioning a set of $m$ elements to $n$ partitions. So,

$S(m,1) = S(m,m) = 1$

$S(m,n) = S(m-1, n-1) + n S(m-1, n)$ // This needs explanation

So, $S(3,2) = S(2,1) + 2S(2,2) = 1+ 2 = 3$. 

So, we get the triangle

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1

which can be extended as required using the formula $S(m,n) = S(m-1, n-1) + n S(m-1, n)$

Answer 2

Given A = { 1 , 2 , 3 , 4 , 5 , 6 }

and B = { 1 , 2 , 3 , 4 , 5 }

so cardinality of A , say m  =  6 and

   cardinality of  B , say n   =  5.

Now we have to calculate no of surjective functions f : A --> B with the additional constraint that f(6) = 3.

Thus we have to ensure that 6 of A is not mapped to any other element of B except 3.

So there are two ways :

1. map 6 to 3 then consider other 5 elements from set A maps to Any elemets to B.(3 is mapped by other also)

2.map 6 to 3 then consider other 5 elements from set A maps to 4 elemets to B except 3.(3 is not mapped by other also)

Let m = 5 (excluded the element 6) and n = 5.We know if a set A contains m elements and B contains n elements , then number of onto (surjective) functions from A to B :

=  n^m  -  ⁿC₁(n-1)^m  + ⁿC₂(n-2)^m........[We continue finding sum till n - k does not becomes 0 and this result comes from inclusion exclusion principle ]

1st case: So substituting n = 5 , m = 5 , we have :

No of onto functions = 5⁵   -   ⁵C₁(4)⁵ +  ⁵C₂(3)⁵  -  ⁵C₃(2)⁵  +  ⁵C₄(1)⁵

                                        = 3125  -  5 * 1024  +  10 * 243  -  10 * 32  +  5

                              = 120

2nd case: So substituting n = 5 , m = 4 , we have :

No of onto functions = 4⁵   -   ⁴C₁(3)⁵ +  ⁴C₂(2)⁵  -  ⁴C₃(1)⁵ 

                                        = 1024  -  4 * 243  +  6 * 32  -  4 

                              = 240

Therefore ,

Total number of onto functions from A to B  =  120 + 240 = 360

Comments

@Habib see my answer. Problem is when we dont consider 3 and later include it, "surjective" formula is no longer valid.

---

@Habib in your solution as you are first seperating 6 from A and calculating Onto function and then adding f(6)=3 back..i think with three always more than one elements are mapping...one is 6 and some others

But what happen if 6 only maps to 3 and Rest all of A i.e {1,2,3,4,5} to rest of B i.e {1,2,4,5}.

Please rectify me if i am wrong

---

now check . i edit he missed only one point :)