I have been able to do the 1st part. I have not been able to prove the 2nd part.
My attempt to the solution :- I took $k$ groups $ a_1, a_2, a_3…, a_k $ Let $a_1$ group has $b_1$ similarly so on..where $b_1+ b_2+…+b_k = n$
Hence it would be ncb1 + ncb2 + ... ncbk (here c stands for combinatorics coeffecient)
But couldn't solve it from here. Please help !
Hint: Start with $n$ elements, then add one more element to get $k$ classes. What are the possibilities?