Combinatorics

Question

There are n hats and k people (where k<n).

$1)$ How many ways we can assign each person a hat?

$2)$ How many ways we can assign each person atleast a hat?

Comments

@Soumya @arvin , Thanks a lot :) , I got confused somewhere at that time b/w distinguishable and indistinguishable. So, sorry for that. I have verified with examples and all are giving same result.

---

i thought i was missing somewhere :) ok brother no problem :)

---

can't we do like this -- as given n hat and k people so each hat can be gievn to k person

so k*k*k*------ n times  = k^n

@srestha mam correct me if wrong

Answer 1

Answer 1) ^(n+k-1)C_(k-1) 

Explanation: Given n hats and k people, Now we can relate this problem to a binary string problem as below.

Lets consider a problem of finding no. of ways we can distribute 3 hats to 3 people.

to represent 3 people we shall take 2 ones in binary, i.e, 11. Now every permutation of 3 zeros and 2 ones is one way to distribute 3 hats among 3 people. Ex:

                       a)01010 means each person gets 1 hat

                       b)00101 means first person gets 2hats, second person 1 hat and third person Zero.

                       c)00011 means first person gets all 3 hats and the second and third doesn't get any hat.

In this way every permutation is one way of distributing.

So. we need to find no. of such permutations. So totally we have for 3 people 2 ones and for 3 hats 3 0s.

For k people k-1 ones, and for n hats n zeros.

So we need to select k-1 places out of n+k-1 places this can be done in ^(n+k-1)C_(k-1)

2)

we can relate this problem to x1+x2+x3+....+xk=n where x1>=1,x2>=1,...xk>=1.

let y1=x1-1, y2=x2-1, ...,yk=xk-1.

y1+y2+y3+.....yk=x1-1+x2-1+x3-1+.....xk-1

y1+y2+...+yk=x1+x2+...+xk-k

y1+y2+.....yk=n-k

where y1>=0,y2>=0...

let n-k=m

no. of ways we could distribute m among k entities( similar to above prob) is ^k+m-1C_m 

i.e, ^k+n-k-1C_n-k =^n-1C_k-1