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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.