Permutations and Combinations
Patrick McAtee, Tom Rice, and Jesse Whidden

Combinations with Repetition

These types of combinations are useful when we have more than one of several different items, and we want to know how many different ways there are to do something.

This idea is best demonstrated with the use of an example:

Suppose you were about to engage in a Nerf war. To prepare for this flying foam armageddon, you must arm yourself with 6 Nerf guns. However, your arsenel only has 4 different types of weapons. How many different ways are there to choose 6 Nerfs from the 4 types available?

Instead of thinking about the math right now, let's come up with a way to draw a picture of what we have:

(TYPE I NERF)|(TYPE II NERF)|(TYPE III NERF)|(TYPE IV NERF)

We'll use the | to separate each of the four Nerf types. Also, we'll use * for each Nerf of that type that we have. If we don't have any of those Nerfs, we'll leave the space blank.

For example, if we have

  • 2 Type I Nerfs
  • 0 Type II Nerf
  • 3 Type III Nerfs
  • 1 Type IV Nerf

we draw:

* * | | * * * | *

Or, if we have

  • 0 Type I Nerfs
  • 4 Type II Nerfs
  • 2 Type III Nerf
  • 0 Type IV Nerfs

we draw:

| * * * * | * * |

Now, instead of thinking of the picture as stars and bars, look at the 9 different positions - each one can have either a star or a bar:

_ _ _ _ _ _ _ _ _

When we draw the pictures of the different Nerf combinations we have, all we're really doing is picking which spots we want to put the stars in! At this point, things should start to look familiar - our Nerf gun problem is now exactly like the combinations from the previous section, when we didn't have to worry about repetition!

Solution:

In this case, there are 9 positions and we need to place 6 objects (the *s). We can use the C(9,6) formula from the previous section to determine there are 84 different combinations of a 6-Nerfs large arsenel.

Theorem

To generalize for an r-combination with repetition, when you have n things to choose from and you are going to pick r items:


# of r-combinations = C(n + r - 1, r)

This formula is very similar to the one used by r-combinations without repetition. In fact, it is easy to see the relationship. Because of this, it is very important before you start solving the problem to determine whether or not repetitions are allowed, given the constraints of the problem. As a general note, repetitions will be allowed when you are selecting a small sample from a large population of items.