I recently received the following interesting problem from Shadowcat, which is a generalization of the cookie problem I’ve written about previously. We again want to count the ways to distribute identical cookies to non-identical students, with the twist that we impose an upper bound on the number of cookies received by each student (quite reasonable if we want to be mindful of the students’ nutrition):
Imagine that instead of ten cookies and five students, you have fifty cookies and ten students. (It’s easier to quantify this situation using larger numbers.) How many ways can you distribute these cookies among the students so that no student has any more than ten cookies?
Students may be given any number of cookies less than or equal to ten, including zero. The cookies are identical, just as in the original problem, so, as with the original problem, it doesn’t matter which cookie the student gets, just how many. But the students, again, are *not* identical, so which student gets a specific number of cookies is important.
I unfortunately haven’t had much time to think about it yet. Feel free to leave comments, thoughts, partial solutions, and solutions in the comments!
The Math Less Traveled 
Let L=10
D(0,s) = 1
D(c,1) = {0 if c>L, 1 otherwise}
D(c,s) = \sum_{k=0}^{\min(c,L)} D(c – k, s – 1)
It seems as though we can take the original solution (the “stars and bars” method as I have always heard it called) and add the principal of inclusion and exclusion as follows.
Similar to the original problem, there are
ways to distribute the cookies to the 10 students.
Next, suppose that the first student gets at least 11 cookies. We can count the number of ways this happens by giving him 11 and then using the remaining 39 cookies to distribute amongst all 10 students. So there are
ways that the first student gets at least 11 cookies. We can do this for each of the 10 students to get that there are 
ways that at least one student gets 11 cookies.
The only problem remaining is that we may have double counted some situations when doing the previous argument, so we have to add back in the ways that at least 2 students get at least 11 cookies. We can do this by giving the two students 11 cookies each and then giving out the remaining 28 cookies to all 10 students. We need to do this for each pair, so we add back
.
We continue the same process with 3 students, 4 students, etc, until we run out of cookies. This tells us that the number should be
So there are 1,018,872,811 ways to distribute 50 cookies to 10 students so that no student gets more than 10 cookies.
Disclaimer: I only count this as a partial solution because I have not done a very good job of checking my work or my reasoning. There are few things that always get me off track when doing this type of counting, so if you have suggestions or corrections, I welcome them. Thanks.
While I couldn’t figure it out mathematically, I did figure it out programatically. The answer I arrived at was the same as yours, so I can verify that your answer, at least, is correct.
I was close to arriving at the same answer you did mathematically, too, but I just couldn’t figure out how to account for the duplicate cases. Thanks for putting the missing pieces into place for me! Your answer makes perfect sense to me.
I agree with you.
Let c=10, s=2 and L=10. The general formula for D(c,s) is:
sum
(-1)^k Binomial[s, k] Binomial[c+s-1-k*(L+1), s-1]
k=0 to Floor[c/(L+1)]+1
Here is my Python code: http://codepad.org/nhkEgK91
It works great: I mean a closed formula is far faster than a mere dynamic programming recursive formula… of course!
Ah, good old PIE!
@wok,
I am not a programmer, so this question is sincere: Why do you use the for-loop to compute the binomial coefficients instead of the closed formula. Is the for-loop really faster? Let me know if you get a chance. Thanks.
@wok,
disregard my last question, that was stupid… it is still too early in the morning for me.
It’s just a step removed from how many 10 digit numbers have the property that the sum of their digits is 50
(I would have worked Tom’s way. It’s in the text, with exercises of Ivan Niven’s “How to Count Without Counting” that serves as a textbook for a senior elective I teach.)