1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can someone please explain to me how to do combinations?

  1. Dec 28, 2009 #1
    Can someone please explain to me how to do combinations?
     
  2. jcsd
  3. Dec 28, 2009 #2
    Re: Combinations

    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.
     
  4. Dec 28, 2009 #3
    Re: Combinations

    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.
     
  5. Dec 28, 2009 #4
    Re: Combinations

    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: Dec 28, 2009
  6. Dec 28, 2009 #5
    Re: Combinations

    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.
     
  7. Dec 28, 2009 #6
    Re: Combinations

    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.
     
  8. Dec 28, 2009 #7
    Re: Combinations

    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]))
     
  9. Dec 28, 2009 #8
    Re: Combinations

    Choosing 3 of 6 items, you should get 20 combinations or 120 permutations.
     
  10. Dec 28, 2009 #9
    Re: Combinations

    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.
     
  11. Dec 28, 2009 #10
    Re: Combinations

    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:
    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)
     
  12. Dec 28, 2009 #11
    Re: Combinations

    Those are permutations, not combinations. There is ONLY one combination of 2 'a' and a 'b', and that is 'aab'.
     
  13. Dec 28, 2009 #12
    Re: Combinations

    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.
     
  14. Dec 30, 2009 #13
    Re: Combinations

    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.
     
  15. Dec 30, 2009 #14
    Re: Combinations

    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)!
     
  16. Dec 30, 2009 #15
    Re: Combinations

    That's why I said the example is poorly worded. But that's irrelevant since the fact remains that the method works.
     
  17. Dec 30, 2009 #16
    Re: Combinations

    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 this great discussion with others via Reddit, Google+, Twitter, or Facebook