Q.How many ways one can select three gift vouchers from a box containing Rs. 100, Rs. 500, Rs. 1000 and Rs. 2000 gift vouchers? Assume that the order in which the vouchers are chosen does not matter, the vouchers of each denomination are identical and there are at least three gift vouchers of each type.

Combination with Repetition

Imagine you walk into a bakery that sells three kinds of pastries: croissant, muffin, and danish. You want to buy four pastries, and you can pick any kind as many times as you like. How many different selections can you make?

This is the core question. You are choosing 4 items from 3 types, where repetition is allowed, and the order in which you pick them does not matter. A selection like {croissant, croissant, muffin, danish} is the same as {muffin, croissant, danish, croissant}. Only the count of each type matters.

The Intuition: Stars and Bars

The classic way to think about this is with stars and bars. Each pastry you buy is a star ($*$). The different types of pastries are separated by bars ($|$).

For three types, you need two bars to create three compartments. For example:

• 2 croissants, 1 muffin, 1 danish → $**|*|*$
• 4 croissants, 0 muffins, 0 danish → $****||$
• 0 croissants, 2 muffins, 2 danish → $|**|**$

Every selection of 4 pastries from 3 types corresponds to a unique arrangement of 4 stars and 2 bars. The number of such arrangements is simply the number of ways to choose which 2 positions (out of the total $4+2 = 6$ positions) will be bars.

That number is $\binom{4+3-1}{3-1} = \binom{6}{2} = 15$.

The Precise Statement

Definition: A combination with repetition (also called a multiset or a combination with replacement) is a selection of $r$ objects from a set of $n$ distinct types, where:

• The same type can be chosen more than once (repetition allowed).
• The order of selection does not matter.

Formula: The number of such selections is

Why It Works (The Proof)

We want the number of non-negative integer solutions to:

where $x_i$ is the number of times type $i$ is chosen. Each solution corresponds to exactly one selection.

Represent each solution with $r$ stars and $n-1$ bars. The total number of symbols is $r + (n-1)$. Choosing the positions of the $n-1$ bars (or the $r$ stars) gives: …