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