As there are 5 different peoples and 3 distinct rooms are there and each room containing 1 person atleast.
it is nothing but #onto functions from peoples(m) to rooms(n).
here (m,n) = (5,3)
# onto fun = (-1)^0* 3C0*(3-0)^5 * (-1)^1* 3C1*(3-1)^5 * (-1)^2* 3C2*(3-2)^5
= 3^5 – 3*32 + 3
= 150.
# onto functions = total functions – non onto functions
Suppose we have a function which maps A to B
let cardinality of A = m and that of B =n (m>=n)
so total # functions will be = n^m ( RHS^LHS)
let m=5(p1,p2,p3,p4,p5) and n=3(x1,x2,x3)
There are three ways in which we can skip 1 element of RHS
- take x1 and x2 and skip x3 (i.e only x1 and x2 are having pre images)
- take x2 and x3 and skip x1 (i.e only x2 and x3 are having pre images)
- take x1 and x3 and skip x2 (i.e only x1 and x3 are having pre images)
So, total non onto function here = 3C1 * 2^5
There are three ways in which we can skip 2 element of RHS
- take x1 and skip x2 and x3 (i.e only x1 having pre image)
- take x2 and skip x3 and x1 (i.e only x2 having pre image)
- take x3 and skip x1 and x2 (i.e only x3 having pre image)
So, total non onto function here = 3C2 * 1^5
NOW as,
# onto functions = total functions – non onto functions
= 3^5 – 3C1*2^5 + 3C2 *1^5
we can write it as,
=(3-0)^5 – 3C1(3-1)^5 + 3C2(3-2)^5
=(n-0)^m – nC1(n-1)^m + nC2(n-2)^m
it can be generalised as,
(i=0 to n)Σ (-1)^i * nCi * (n-i)^m