Find the number of into functions

Question

Answer 1

The question is asked indirectly that given set A contains m elements and B contains n elements , no of into functions(non surjective) is given as :

ⁿC₁ * (n-1)^m -  ⁿC₂ * (n-2)^m  + ⁿC₃ * (n-3)^m -  ..................[From inclusion exclusion principle] ....(1)

Substituting m = 5 and n = 4 , we have :

No of into functions = ⁴C₁ * 3⁵  -   ⁴C₂ * 2⁵   +   ⁴C₃  * 1⁵

                                       =  4 * 243  - 6 * 32 + 4

                             =  972  -  192 + 4

                             =  784

Hence , 784 should be the correct answer.

Comments

i didn’t understand inclusion exclusion part, someone please explain exculsion part.

Answer 2

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$

Total number of into(not surjections) functions $=$ total functions $-$ onto functions $=1024-240=784$