Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
In the last class, you were working on part (a) when class ended. Can you explain how it works?
Sure. Recall that R(r,k) is the number of ways to partition r into k parts. Split up these partitions into two possible types: those that involve a 1 and those that do not:
R(r,k) = ( Number of partitions of r into k parts, at least one of which is 1 ) + (Number of partitions of r into k parts, all of which are at least 2)
The first part on the right is simply R(r-1,k-1), the number of ways to partition r-1 into k-1 parts (then add in a 1 and you get a partition of r into k parts with at least one 1). The second part on the right is slightly trickier. If we subtract 1 from each of the k parts of this partition, we get a partition of r-k into k parts. (And vice versa: a partition of r-k into k parts will give a partition of r into k parts, all of which are at least 2, simply by adding one to each of the parts.) Thus the second number on the right is R(r-k,k).