- #1

- 328

- 0

Can someone please explain to me how to do combinations?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter ƒ(x)
- Start date

- #1

- 328

- 0

Can someone please explain to me how to do combinations?

- #2

- 105

- 0

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.

- #3

- 754

- 1

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:

[tex]\frac{X!}{Y! (X-Y)!}[/tex]

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:

[tex]\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[/tex]

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.

- #4

- 354

- 2

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).

Last edited:

- #5

- 754

- 1

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.

- #6

- 754

- 1

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.

- #7

- 754

- 1

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]))

- #8

- 754

- 1

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

- #9

- 754

- 1

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

[tex]\frac{X!}{(X-Y)!}[/tex]

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

- #10

- 354

- 2

Woops.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.

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:

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

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)

- #11

- 105

- 0

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'.

- #12

- 105

- 0

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 excercise 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.

- #13

- 754

- 1

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

- #14

- 754

- 1

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)!

- #15

- 354

- 2

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 6differently coloredsocks. 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.

- #16

- 754

- 1

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.

Share: