### 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.