Combinations - order doesn't matter, repetitions allowed

[fleazo]

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

 

[Simon Bridge]

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.

 

[fleazo]

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


thanks for the reply btw

 

[Stephen Tashi]

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.

 

[fleazo]

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)

 

[Simon Bridge]

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.

 

[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

 

[micromass]

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.

 

[fleazo]

thank you all for the responses. It cleared up the issue!

 

[cepheid]

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 doesn't seem to appear in any posts. Unless I am just going crazy.

 

[Simon Bridge]

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.

 

[Simon Bridge]

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 doesn't seem to appear in any posts. Unless I am just going crazy.

I did point it out but I think I deleted it in an edit - which may be where you saw it - I thought OP understanding was more important than instruction in putting numbers into equations and didn't want to distract him. I wish I'd thought of micromass' one.

I'm glad someone pointed it out in the end too :)

 

[Edgardo]

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