# Combinations - order doesn't matter, repetitions allowed

 P: 66 I'm trying to figure out the formula I need... ok, say that r=5, so there are 5 items {A,B,C,D,E} And we want to chose 5 of those Order doesn't matter, repitions allowed so for example {A,A,A,B,B} is a feasible solution {A,B,C,D,E} is feasible so on But the formula (n+r-1)!/r!(n-1)! doesn't work because here n=r so it becomes (2n-1)!/(2n-1)! = 1. Also, what happens when I want to put certain restrictions. Like for example, say I want an example of the above format with the exception that A and B can only be chosen if C is chosen. I know I would just find all those infeasible solutions and subtract them but I have a hard time finding those infeasibles. I mean, that situation seems obviosu but what if it has to do with ranking. Like say, A chosen --> B,C,D,E, are chosen. B chosen --> C,D,E chosen. D chosen --> E chosen. So what if there are n such rules. Do I make a case for each individually? I suck at these stupid things
 Homework Sci Advisor HW Helper Thanks P: 12,775 You want John Allen Paulos: Innumeracy ... no really: he has a good guide to handling these things using a simple multiplication rule. It'll be in a library near you. You have 5 slots, which can each have one of 5 possible entries. Thats 5x5x5x5x5 possible combinations. For the restrictions, you do pretty much have to work out the possible combinations with the forbidden configuration and subtract them off. Just go systematically. It takes practise.
P: 66
 From that formula, you wanted to pick a combination of 5 from 5 things ... so n=5 and r=5 so the formula becomes 9!/(5!x4!)=126 so I don't know what you were doing.

Sorry about that... complete brain fail on my part!!

sorry but i'm confused about how it would be 5X5X5X5X5

I'm talking about a situation where the order is irrelevant and permutations can occur

P: 3,285
Combinations - order doesn't matter, repetitions allowed

 Quote by fleazo I'm talking about a situation where the order is irrelevant and permutations can occur
I don't think "permutations can occur" is the right phrase.

I think an example of what you are asking is this:

If we multiply out the expression $(A + B + C + D + E)^5$ and combine like terms, how many distinct types of terms will there be? For example $AB^2C^2$ and $C^2A B^2$ are like terms. $AB^2C^2$ and $A^2B^2C$ are unlike terms.

So you are asking about the number of different types of terms, not about the numerical coefficients of the various types of terms.
 P: 66 I apologize, I completely misspoke. I meant to say "repetitions can occur" I mix up similar sounding words like that all the time and don't realize it. THe only reason I was confused about the 5X5X5X5X5 thing was because that formula (n+r-1)!/r!(n-1)! I thought was specifically used for that situation (given n items, you want to chose r so that repetitions can occur and order is irrelevant)
 Homework Sci Advisor HW Helper Thanks P: 12,775 Imagine it was only 2 slots. You can do that right? Order doesn't matter, and repititions are allowed, so {AB, AA, BA} is three combinations. You get a total of 5x5=25 possible combinations. If you could not get doubles, then it would be 5x4=20 combinations - since whichever of the 5 get the first slot will leave only 4 for the second. Now extrapolate to 5 slots.
 P: 66 i see what you are saying, but it seems like by that logic order should matter. The example you were giving with 2 slots, it seemed like the goal is: there are 5 objects {A,B,C,D,E} and 2 slots. So you were saying there are 5X5 possibilities. But then that would include for example both AB and BA, but I'm talking about order being irrelevant so only one could be included
 Mentor P: 18,240 This is one of more difficult combinatorial problems... Here is how you solve it: Let's first introduce a notation. I write | all the A's | all the B's | all the C's | all the D's | all the E's | So for example, (A,A,A,B,C) is written as |AAA|B|C||| and (A,C,D,E,E) is |A||C|D|EE| But we can simplify this notation!! Indeed, under this notation, we don't have to write the A, B, etc. anymore. So I know that |.|||....|.| represents (A,D,D,D,D). So right now we have 11 spots: ........... and we want choose 6 spots where to put |. Under the constraints that the first and the last symbol are |. So (disregarding the firsst and last symbol): we have 9 spots, and we want to choose 4 spots where to put | Every choice of spots will induce uniquely one of the permutations you want. So we see that $\binom{9}{4}$ is the required probability.
 P: 66 thank you all for the responses. It cleared up the issue!
 Emeritus Sci Advisor PF Gold P: 5,196 Am I the only one who thinks the OP had the right equation for combination with repetition in the first place, and was just using it wrong? If I start with (n+r-1)! / (r!(n-1)!) And I plug in n=r=5, I get (10-1)! / (5! (5-1)!) = 9! / (5!4!) Which is just "9 choose 4", the exact same thing as micromass derived. Micromass just showed how to derive the combinatorial equation that the OP had in the first place! People who were telling him/her that it would be 5^5 were way off. That would be for permuation with repetition rather than combination with repetition. I.e. 5^5 would be true if order mattered, but it doesn't. EDIT : I re-read the thread and see that nobody was telling him that the *answer* should be 5^5, it just came up as part of the explanation. I also see that Simon Bridge pointed out the same misuse of the equation as I did. OK. EDIT 2: or at least *somebody* pointed it out. It's not clear who, because it's quoted but it doesnt seem to appear in any posts. Unless I am just going crazy.
Homework
HW Helper
Thanks
P: 12,775
 Quote by fleazo i see what you are saying, but it seems like by that logic order should matter. The example you were giving with 2 slots, it seemed like the goal is: there are 5 objects {A,B,C,D,E} and 2 slots. So you were saying there are 5X5 possibilities. But then that would include for example both AB and BA, but I'm talking about order being irrelevant so only one could be included
Ah - that's what I was worried about when I gave that as my example.
So you want AB and BA to count as one.

By the example I presented:

(5x5-5)/2 +5 ; removing the bottom half of the square but keeping the diagonal.

But you have a more elegant description from the very small one.
Homework
 P: 685 I like your derivation micromass! Here are all 126 = $9 \choose 4$ combinations. Note: I've used the notation by micromass. Examples: o|o|o|o|o means A | B | C | D | E giving the combination ABCDE o|o||oo|o means A | B | | DD | E giving the combination ABDDE 1 ooooo|||| AAAAA 2 oooo|o||| AAAAB 3 oooo||o|| AAAAC 4 oooo|||o| AAAAD 5 oooo||||o AAAAE 6 ooo|oo||| AAABB 7 ooo|o|o|| AAABC 8 ooo|o||o| AAABD 9 ooo|o|||o AAABE 10 ooo||oo|| AAACC 11 ooo||o|o| AAACD 12 ooo||o||o AAACE 13 ooo|||oo| AAADD 14 ooo|||o|o AAADE 15 ooo||||oo AAAEE 16 oo|ooo||| AABBB 17 oo|oo|o|| AABBC 18 oo|oo||o| AABBD 19 oo|oo|||o AABBE 20 oo|o|oo|| AABCC 21 oo|o|o|o| AABCD 22 oo|o|o||o AABCE 23 oo|o||oo| AABDD 24 oo|o||o|o AABDE 25 oo|o|||oo AABEE 26 oo||ooo|| AACCC 27 oo||oo|o| AACCD 28 oo||oo||o AACCE 29 oo||o|oo| AACDD 30 oo||o|o|o AACDE 31 oo||o||oo AACEE 32 oo|||ooo| AADDD 33 oo|||oo|o AADDE 34 oo|||o|oo AADEE 35 oo||||ooo AAEEE 36 o|oooo||| ABBBB 37 o|ooo|o|| ABBBC 38 o|ooo||o| ABBBD 39 o|ooo|||o ABBBE 40 o|oo|oo|| ABBCC 41 o|oo|o|o| ABBCD 42 o|oo|o||o ABBCE 43 o|oo||oo| ABBDD 44 o|oo||o|o ABBDE 45 o|oo|||oo ABBEE 46 o|o|ooo|| ABCCC 47 o|o|oo|o| ABCCD 48 o|o|oo||o ABCCE 49 o|o|o|oo| ABCDD 50 o|o|o|o|o ABCDE 51 o|o|o||oo ABCEE 52 o|o||ooo| ABDDD 53 o|o||oo|o ABDDE 54 o|o||o|oo ABDEE 55 o|o|||ooo ABEEE 56 o||oooo|| ACCCC 57 o||ooo|o| ACCCD 58 o||ooo||o ACCCE 59 o||oo|oo| ACCDD 60 o||oo|o|o ACCDE 61 o||oo||oo ACCEE 62 o||o|ooo| ACDDD 63 o||o|oo|o ACDDE 64 o||o|o|oo ACDEE 65 o||o||ooo ACEEE 66 o|||oooo| ADDDD 67 o|||ooo|o ADDDE 68 o|||oo|oo ADDEE 69 o|||o|ooo ADEEE 70 o||||oooo AEEEE 71 |ooooo||| BBBBB 72 |oooo|o|| BBBBC 73 |oooo||o| BBBBD 74 |oooo|||o BBBBE 75 |ooo|oo|| BBBCC 76 |ooo|o|o| BBBCD 77 |ooo|o||o BBBCE 78 |ooo||oo| BBBDD 79 |ooo||o|o BBBDE 80 |ooo|||oo BBBEE 81 |oo|ooo|| BBCCC 82 |oo|oo|o| BBCCD 83 |oo|oo||o BBCCE 84 |oo|o|oo| BBCDD 85 |oo|o|o|o BBCDE 86 |oo|o||oo BBCEE 87 |oo||ooo| BBDDD 88 |oo||oo|o BBDDE 89 |oo||o|oo BBDEE 90 |oo|||ooo BBEEE 91 |o|oooo|| BCCCC 92 |o|ooo|o| BCCCD 93 |o|ooo||o BCCCE 94 |o|oo|oo| BCCDD 95 |o|oo|o|o BCCDE 96 |o|oo||oo BCCEE 97 |o|o|ooo| BCDDD 98 |o|o|oo|o BCDDE 99 |o|o|o|oo BCDEE 100 |o|o||ooo BCEEE 101 |o||oooo| BDDDD 102 |o||ooo|o BDDDE 103 |o||oo|oo BDDEE 104 |o||o|ooo BDEEE 105 |o|||oooo BEEEE 106 ||ooooo|| CCCCC 107 ||oooo|o| CCCCD 108 ||oooo||o CCCCE 109 ||ooo|oo| CCCDD 110 ||ooo|o|o CCCDE 111 ||ooo||oo CCCEE 112 ||oo|ooo| CCDDD 113 ||oo|oo|o CCDDE 114 ||oo|o|oo CCDEE 115 ||oo||ooo CCEEE 116 ||o|oooo| CDDDD 117 ||o|ooo|o CDDDE 118 ||o|oo|oo CDDEE 119 ||o|o|ooo CDEEE 120 ||o||oooo CEEEE 121 |||ooooo| DDDDD 122 |||oooo|o DDDDE 123 |||ooo|oo DDDEE 124 |||oo|ooo DDEEE 125 |||o|oooo DEEEE 126 ||||ooooo EEEEE