Ace Book for Discreet Mathematics , Combinatorics.

Question

Number of ways to assign 5 different people in 3 different rooms, so that each room contains at least one person?

Comments

https://gateoverflow.in/381403/combinatorics-problem-2

---

(5!/2!2!1!)*3 +(5!/1!1!3!)*3

90+60=150

Answer 1

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

Comments

Can you add why/how this formula came for number of onto functions?

---

shishir__roy

# 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