Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number M (1, 2 or 3) is fixed.]

T N C M

Sample Input:

3 5 3 1 5 2 2 6 2 3

Sample Output:

25 10 10

I defined dp[i][j] as the number of ways of distributing i coins to j charities. Then, a recursion relation should be derived in each of these three cases:

So for 1 at least 1 coin dp[i][j]=j∗dp[i−1][j]+dp[i−1][j−1]

I am unable to figure out the recurrence relation for at least 2 coins and at least 3 coins. Can you please explain the other two recurrence relation by clearly defining each states and transitions. I would be highly obliged to you and much of time will be saved.

Thank You

Sample Input ( T followed by N C M where N is the total number of unique coins and C is the number of identical charities and M is the number of coins each charity at least gets (it is either 1, 2 , 3). Sample Input : 3

5 3 1

5 2 2

6 2 3 Sample Output : 25 10 10