Associated Topics || Dr. Math Home || Search Dr. Math

### Combinations and Permutations with Replacement

```Date: 02/01/2004 at 17:07:01
From: John
Subject: Combinations/Permutations with Replacement

I have found the formulas for permutations and combinations but both
formulas appear to be for the cases where there is no replacement:

N!                 N!
C = --------  and   P = ------
n!(N-n)!            (N-n)!

Do you know the formulas for "with replacement"?

For example, without replacement:

N            N
C  = 10  and P  = 20 (where N = 5 and n = 2)
n            n

If you allow for replacement, C and P both increase by 5.  True?
```

```
Date: 02/02/2004 at 11:22:51
From: Doctor Vogler
Subject: Re: Combinations/Permutations with Replacement

Hi John,

You are correct that

5-C-2 = 10, and
5-P-2 = 20,

and you are correct that

5-C-2 with replacement = 15, and
5-P-2 with replacement = 25.

But adding 5 does not work for every N and n.

For the second case, N-P-n with replacement, the problem is really
quite simple.  You want to count how many ways there are to choose n
items out of N total, where the order is important.  In other words,
there are N ways to choose the first item, N ways to choose the
second, and so on through N ways to choose the n'th item.  So we
conclude:

N-P-n with replacement = N^n.

That's why we don't have special notation for that; it's just an
exponent, N to the n.  When order is not important, in the case of
N-C-n with replacement, the situation is a little more complicated.

What we typically do for something where order is not important is to
count the ways where order *is* important and then divide by the
number of reorderings that give the same set of values.  But when
there is repetition in some choices and not in others, that number of
reorderings is not constant.  So the best way that I can think of is
to consider the possible kinds of repetitions:

In the case of 5-C-2 with replacement, there are 5-C-2 = 10 ways
without any repeats, and 5-C-1 = 5 ways with the same item chosen
twice, for a total of 15.

In general, for N-C-n with replacement, you first need to find all of
the "partitions" of n, that is, the number of ways you can add up
integers and get n.  This gives you all the possible repeat patterns.

For example, if n=4, then there are five partitions, namely
1+1+1+1 (four different items), 2+1+1 (one item twice and two others
once each), 2+2 (two items twice each), 3+1 (one item three times and
one once), and 4 (one item all four times).  For each partition, the
number of ways to choose items according to that repeat pattern equals
the number of ways to choose one item for each number in the sum
divided by the number of ways to reorder all the similar numbers.

In other words, you count the number k of numbers in the sum and take
N-P-k.  Then for each number that appears in the sum, you count how
many times m that it appears in the sum and divide by m!.  For
example, for 10-choose-4 with replacement, we get

1+1+1+1: (10-P-4)/4!   = 10-C-4   = 10!/6!4! = 210

2+1+1:   (10-P-3)/2!1! = 10*9*8/2 = 360

2+2:     (10-P-2)/2!   = 10*9/2   = 45

3+1:     (10-P-2)/1!1! = 10*9     = 90

4:       (10-P-1)/1!   = 10

for a grand total of 10+90+45+360+210 = 715.

If you have any questions or need more help, please write back and
show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/02/2004 at 16:48:35
From: John
Subject: Thank you (Combinations/Permutations with Replacement)

You are the man!  I suspected the answer would be something simple and
something difficult!  I am indebted to you and your wisdom.  Thanks!

John
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search