Combinatorics. Counting the number of functions, injections, and surjections. id
ID: 3196032 • Letter: C
Question
Combinatorics.
Counting the number of functions, injections, and surjections.
identical objects into distinct containers.
Suppose there are n identical balls and we want to place them into k distinct bins.
1a.) What is the total number of functions that places the n identical balls into the k distinct bins?
1b.) How many functions are there such that 1 ball goes into exactly 1 of the k distinct bins? (Number of injections)
1c.) How many functions are there such that no bin is left empty? (Number of surjections)
Explanation / Answer
1a.) First consider 1 ball then we can place that ball in any of the k distinct bins.ie. there are k no. of possibilities.And for the 2nd ball also there are k no. of possiblities and similarly for 3rd ball also has k no. of possibilities, and so on.
Then total no. of functions is equal to k*k*k....k(n times)= kn..
1c.) first place 1 ball in eah of the k distinct bins. This can be done in 1 way(sinse balls are identical).Then we can place remaining n-k balls in k bins in different ways. Then total no. of functions is