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-1Cm
i.e, k+n-k-1Cn-k =n-1Ck-1