Combinations with repetition

The number of such selections is \(\binom{n+k-1}{k}\). To see it, represent each selection with \(k\) stars and \(n-1\) bars separating the types. For example, with 3 types and 5 objects, \(\star\star|\star|\star\star\) means 2 of the first, 1 of the second and 2 of the third. Each selection is a row of \(k+n-1\) symbols in which the \(k\) star positions are chosen, which gives \(\binom{n+k-1}{k}\).

The same count solves equations: the nonnegative integer solutions of \(x_1+\dots+x_n=k\) are the selections of \(k\) objects from \(n\) types, where \(x_i\) counts how many of type \(i\) there are. With lower bounds, subtract first: for \(x_i\ge 1\) substitute \(y_i=x_i-1\), leaving \(k-n\) units to distribute. If the condition is an inequality \(\le\), add a slack variable.

It helps to compare with the other counts: ordered with repetition gives \(n^k\); ordered without repetition, \(n!/(n-k)!\); unordered without repetition, \(\binom{n}{k}\); and unordered with repetition, \(\binom{n+k-1}{k}\). Typical mistake: using \(\binom{n}{k}\) when elements may repeat, or \(n^k\) when order does not matter.