Dark Mode

0 votes

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**

**# 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**

0