Can someone please explain to me how to do combinations?

[ƒ(x)]

Can someone please explain to me how to do combinations?

 

[Mensanator]

With or without replacement?
You know the difference between combinations and permutations, right?

combinations without replacement:

>>> n = 'abcdef'
>>> for i in n:
for j in n:
for k in n:
if i<j and j<k:
print(''.join([i,j,k]))


abc
abd
abe
abf
acd
ace
acf
ade
adf
aef
bcd
bce
bcf
bde
bdf
bef
cde
cdf
cef
def

Note that each is in alphabetical order. If you wanted permutations, in addition to 'def' you also have 'dfe', 'edf', 'efd', 'fde', 'fed' and so on. Also note within each triplet, no letter is duplicated (that's what 'without replacement' means).

If you want 'with replacement' use this:

>>> for i in n:
for j in n:
for k in n:
if i<=j and j<=k:
print(''.join([i,j,k]))


aaa
aab
aac
aad
aae
aaf
abb
abc
abd
abe
abf
acc
acd
ace
acf
add
ade
adf
aee
aef
aff
bbb
bbc
bbd
bbe
bbf
bcc
bcd
bce
bcf
bdd
bde
bdf
bee
bef
bff
ccc
ccd
cce
ccf
cdd
cde
cdf
cee
cef
cff
ddd
dde
ddf
dee
def
dff
eee
eef
eff
fff

Note that as combinations, each triplet is still in alphabetical order, but since replacent is allowed, you also get those triplets with repeated letters.

 

[zgozvrm]

A combination is the number of ways "X" items can be arranged into groups of "Y".

This means that order is not unique.

If you have 5 items A, B, C, D, and E, how many combinations of 3 are there? Since order is not unique, ABC, ACB, BAC, BCA, CAB, and CBA are all the same combination: they all represent the group of 3 items containing A, B and C.

To calculate the number of possible combinations, you must use the factorial function, "x!" This is the function that takes the positive integer entered and multiplies it by the the next smaller integer then multiplies the result by the next smaller integer, repetitively, until it is multiplied by 1. For example, 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720.

Now, to find the number of combinations of Y items in a set of X total items, use the formula:

\frac{X!}{Y! (X-Y)!}


So, in the case of finding how many ways 5 items can be arranged in groups of 3, we have X=5 and Y=3. Plugging in the values gives us:

\frac{5!}{3! (5-3)!} = \frac{5!}{3! \times 2!} = \frac{5\times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)} = \frac{120}{6 \times 2} = \frac{120}{12} = 10

You can verify this by writing out the combinations, never changing the order of the items. For instance, with the set of 5 items, A, B, C, D, & E, you have (starting with A):
ABC, ABD, ABE, ACD, ACE, ADE (then, starting with B):
BCD, BCE, BDE (and starting with C):
CDE

(Notice that the left-to-right order of the items is never reversed from their original order.)

That's a total of 10 combinations.


Most scientific calculators have the factorial function built in. Many also have a "combinations" function built in; mine is shown as "nCr" where n represents the number of items to choose from, and r represents the size of the group. This function helps not only to simplify entering the numbers into the formula, but also allows for larger numbers since 69! is typically the largest value that a calculator can handle. Due to the possibility for simplification, you can use "nCr" to find the number of combinations of 5 items chosen from 75, which normally would cause an overflow using the longhand calculation.

 

[Anonymous217]

A method I've learned from a teacher maybe in like 6th grade is to draw out blanks like so:
__ __ __ __
The # of blanks is the amount of items/slots available. In each slot, you put the # of items/people that can be inside the slot. Always do specified slots first, and then do the rest. Multiply each blank and you have the permutation. Take the permutation and divide by the (# of blanks)! and you get the combination.

For example, John has 3 types of socks, black, red, and white. How many different pairs of socks can he wear?
3 types; 2 slots (it's a pair)
3 2 1 = 6 permutations
6/2 = 3 combinations

Although elementary, this method is essentially using the combination and permutation formulas. I never got used to nCr and nPr types, especially if a problem combines more than one or two permutation/combinations. This is a fantastic way for doing it by hand that is just as fast (unless the # of slots get extremely large).

 

[zgozvrm]

A method I've learned from a teacher maybe in like 6th grade is to draw out blanks like so:
__ __ __ __
The # of blanks is the amount of items/slots available. In each slot, you put the # of items/people that can be inside the slot. Always do specified slots first, and then do the rest. Multiply each blank and you have the permutation. Take the permutation and divide by the # of blanks and you get the combination.

For example, John has 3 types of socks, black, red, and white. How many different pairs of socks can he wear?
3 types; 2 slots (it's a pair)
3 2 1 = 6 permutations
6/3 = 2 combinations

Although elementary, this method is essentially using the combination and permutation formulas. I never got used to nCr and nPr types, especially if a problem combines more than one or two permutation/combinations. This is a fantastic way for doing it by hand that is just as fast (unless the # of slots get extremely large).

This doesn't work.

If you're talking about how many different color combinations of socks John can wear, he has the following possibilities:
Black - Black
Black - Red
Black - White
Red - Red
Red - White
White - White

That's 6 combinations.

If you consider both socks of the same color to be the same sock, then for permutations, there would be only one Black-Black, one Red-Red, and one White-White. This would give:
Black - Black
Black - Red
Black - White
Red - Black
Red - Red
Red - White
White - Black
White - Red
White - White

or 9 permutations.

 

[zgozvrm]

If you want 'with replacement' use this:

>>> for i in n:
for j in n:
for k in n:
if i<=j and j<=k:
print(''.join([i,j,k]))


aaa
aab
aac
aad
aae
aaf
abb
abc
abd
abe
abf
acc
acd
ace
acf
add
ade
adf
aee
aef
aff
bbb
bbc
bbd
bbe
bbf
bcc
bcd
bce
bcf
bdd
bde
bdf
bee
bef
bff
ccc
ccd
cce
ccf
cdd
cde
cdf
cee
cef
cff
ddd
dde
ddf
dee
def
dff
eee
eef
eff
fff

Note that as combinations, each triplet is still in alphabetical order, but since replacent is allowed, you also get those triplets with repeated letters.

Uh, no...

You're program doesn't include several possibilities:
aba
aca
acb
ada
adb
adc
aea
aeb
aec
aed
afa
afb
afc
afd
afe

just to start...

You missed over half of them.

 

[zgozvrm]

Uh, no...

You're program doesn't include several possibilities:
aba
aca
acb
ada
adb
adc
aea
aeb
aec
aed
afa
afb
afc
afd
afe

just to start...

You missed over half of them.

I'm not familiar with the programming language you're using, but it looks like this would work:

for i in n:
for j in n:
for k in n:
print(''.join([i,j,k]))

 

[zgozvrm]

Choosing 3 of 6 items, you should get 20 combinations or 120 permutations.

 

[zgozvrm]

The formula for Y permutations of X items (as opposed to Y combinations of X items) is:

\frac{X!}{(X-Y)!}


This is very similar to the formula for combinations; it is missing the factor of Y! in the denominator.

 

[Anonymous217]

This doesn't work.

If you're talking about how many different color combinations of socks John can wear, he has the following possibilities:
Black - Black
Black - Red
Black - White
Red - Red
Red - White
White - White

That's 6 combinations.

If you consider both socks of the same color to be the same sock, then for permutations, there would be only one Black-Black, one Red-Red, and one White-White. This would give:
Black - Black
Black - Red
Black - White
Red - Black
Red - Red
Red - White
White - Black
White - Red
White - White

or 9 permutations.

Woops. It does work. My example is just poorly worded. By 3 different types of socks, I meant only 1 of each (1 red sock, 1 white sock, and 1 black sock).
If the problem means he has 6 socks (2 of each color), then it goes like this:
6 5 = 30 perm
30/2 = 15 com

Each sock is specific; for example, label them like the following when you're trying to list them out:
B#1, B#2, R#1, R#2, W#1, W#2

Here's an example that's easier to understand:

Choosing 3 of 6 items, you should get 20 combinations or 120 permutations.

6 items; 3 slots.
6 5 4 = 120 permutations.
120/(3!) = 20 combinations.
Same as the calculator or plugging it in the formula. (The method should always work because it IS the formula)

 

[Mensanator]

Uh, no...

You're program doesn't include several possibilities:
aba
aca
acb
ada
adb
adc
aea
aeb
aec
aed
afa
afb
afc
afd
afe

just to start...

You missed over half of them.

Those are permutations, not combinations. There is ONLY one combination of 2 'a' and a 'b', and that is 'aab'.

 

[Mensanator]

I'm not familiar with the programming language you're using, but it looks like this would work:

for i in n:
for j in n:
for k in n:
print(''.join([i,j,k]))

The language was Python. Sorry that the editor destroyed the indenting.

Your idea is the full Cartesian Product, but not the right answer.

All variations of permutations/combinations with/without replacement are subsets of the Cartesian Product. The full Cartesian Product (your example) is "permutations with replacement" and can't be the answer to a query about combinations.

By starting with the three nested for loops, I can generate any of

permutations with replacement
permutations without replacement
combinations with replacement
combinations without replacement

with appropriate filtering (no filtering gives perm w/repl, as in your example). I already showed the appropriate filters for comb w/repl and comb wo/repl. I'll leave it as an exercise for the student to figure out how to filter to give perm wo/ repl.

Of course, I could have simply demonstarted that all four of these functions are built into Python, but then the OP wouldn't learn anything.

 

[zgozvrm]

Woops. It does work. My example is just poorly worded. By 3 different types of socks, I meant only 1 of each (1 red sock, 1 white sock, and 1 black sock).
If the problem means he has 6 socks (2 of each color), then it goes like this:
6 5 = 30 perm
30/2 = 15 com

Still, not a good example though. Most people would not differentiate one red sock from another, therefore there would only be 6 combinations of colors that could be worn. A clearer example would have John choosing any 2 of 6 differently colored socks. In that case, there would, in fact be 15 combinations.

 

[zgozvrm]

Those are permutations, not combinations. There is ONLY one combination of 2 'a' and a 'b', and that is 'aab'.

You're absolutely right. I was thinking about the sock example given by Anonymous217 and took "combinations with replacement" to be the same as permutations which, of course, is not the case.

In the sock example, combinations with replacement would make no sense at all. After all, you can't wear the same sock on both feet (and still get your shoes on)!

 

[Anonymous217]

Still, not a good example though. Most people would not differentiate one red sock from another, therefore there would only be 6 combinations of colors that could be worn. A clearer example would have John choosing any 2 of 6 differently colored socks. In that case, there would, in fact be 15 combinations.

That's why I said the example is poorly worded. But that's irrelevant since the fact remains that the method works.

 

[zgozvrm]

That's why I said the example is poorly worded. But that's irrelevant since the fact remains that the method works.

Agreed. It works. It's merely a simplification of the full formula.

It's generally easier to use the original formula as it takes less steps. That said, what works for some doesn't work for others, and vice-versa.