How to Calculate Combinations with Repetition nHr

Calculates the number of ways to choose r items from n kinds with repetition allowed, nHr = (n + r − 1)Cr. This counts, for example, picking 2 scoops from 3 flavours where the same flavour twice is allowed.

Explanation

Combinations with repetition count the ways of choosing $r$ items from $n$ kinds when the same kind may be picked more than once.

_nH_r = {}_{n+r-1}C_r

This differs from an ordinary combination, where each item can be taken at most once.

Example

Buy 2 scoops of ice cream from 3 flavours (vanilla, chocolate, matcha). Two scoops of the same flavour are allowed.

_3H_2 = {}_{3+2-1}C_2 = {}_4C_2 = \dfrac{4 \times 3}{2 \times 1} = 6

Listing them: two vanilla, two chocolate, two matcha, vanilla with chocolate, vanilla with matcha, chocolate with matcha — six in all.

Where the formula comes from

Think of stars and bars. Write each scoop as a star and each boundary between flavours as a bar, so that "star bar star bar" means one vanilla and one chocolate, and "star star bar bar" means two vanillas.

With 3 flavours you need 2 bars. Together the 2 stars and 2 bars fill 4 positions, and you simply choose which 2 hold stars: $_4C_2$ . In general you arrange $r$ stars and $n-1$ bars, which gives $_{n+r-1}C_r$ .

Where it is used

Shopping where you may take several of the same item
Counting the non-negative integer solutions of $x + y + z = 10$ , which is $_3H_{10}$
Rolling several dice and recording only which faces came up, not which die showed what