edited by
530 views
0 votes
0 votes
Number of ways to assign 5 different people in 3 different rooms, so that each room contains at least one person?
edited by

1 Answer

0 votes
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

  1. take  x1 and x2  and skip x3 (i.e only x1 and x2 are having pre images)
  2. take  x2 and x3  and skip x1 (i.e only x2 and x3 are having pre images)
  3. 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

  1. take  x1 and skip  x2  and  x3 (i.e only x1  having pre image)
  2. take  x2 and skip  x3  and  x1 (i.e only x2  having pre image)
  3. 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

edited by

Related questions

0 votes
0 votes
1 answer
2
Lifesuraj asked Oct 6, 2023
229 views
its output is 6??how?? // Online C++ compiler to run C++ program online#include <iostream>using namespace std;int main() { // Write int a=-3; a=-a-a+!a; cout<...
0 votes
0 votes
1 answer
4
Vegeta asked Sep 13, 2018
934 views
whats ans of this qn and please explain