Lemma

The number of non-negative n-tuples with sum x is

Proof

A standard ``stars and bars'' argument (in Feller's terminology, e.g., p. 38 of [9]) gives the answer. The number of such sequences is equal to the number of ways of arranging n-1 bars and x stars in a row if we interpret the size of each contiguous sequence of stars as a component of the n-tuple and the bars as separating components. The number of such sequences of bars and stars is the same as the number of ways to chose n-1 locations for the bars out of a total of x+n-1 locations, which is just the stated binomial coefficient.