Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [Discrete Math] Permutations / Combinations Advice needed

  1. Apr 11, 2006 #1
    One of the class objectives is to give an oral presentation to the professor. This time it has to do with explaining Permutations and Combinations. We have 4 things we need to explain:

    1) Permutations / Repetitions are not allowed / Order Matters

    2) Combinations / Repetitions are not allowed / Order Doesn't matter

    3) Permutations / Repetitions are allowed / Order Matters

    4) Combinations / Repetitions are allowed / Order Doesn't matter

    Here is what I have so far as far as explainations go:

    1) P(n,k), n = number of objects, k = pickings

    So we permute n, the number of objects... n!, this gives us n(n-1)(n-2)...(n-(k-1))*(n-k)!, so we have the total permutations of n objects. Now we must divide by (n-k)!, since these elements are ones past the kth element.

    This gives us the formula n! / (n-k)!

    2) C(n,k) n choose k.

    We are permuting the n! / (n-k)!, this will give us the permutation of n objects on k elements. Since we cannot have combinations such as 256 and 562, we must eliminate them. We do so by multiplying k! with (n-k)!; so we get n! / (n-k)!k!. My problem here is I can't understand why that k! is there... I know it has something to do how the thing gets ordered, but I can't explain it. Maybe somebody can help me out here.

    3) Example: AABBCA;

    The formula we get is... (m1 + m2 + ... mn)! / (m1!*m2!*...*mn!); and I need to explain how we get that...

    Here we have 3 objects, n = 3.
    We permute all the 'copies' of each object. (3 A's + 2 B's + 1 C)!. This gives us the total permutations. (I need some help explaining that a bit better). What does this 'give us'?...

    Then I know we take that and then we permute each object, by the number of copies, so since we have 3 A's we do 3!, for the B's we have 2!, and for C we have 1!. I by the multilplication principle we multiply them together, 3!*2!*1!; so then we (3 A's + 2 B's + 1 C)! / 3!*2!*1!. I'm a bit lost as to why we divide... I know that it's because order matters, so we can have 245 and 254, they are not the same, and repitions are allowed... But why?...

    4) Here we'll use the 00|000|0, where
    k = number of circles
    number of "|" = n-1
    How many 'types' of objects do we have?... no f'en clue.

    But in the end we plug in k for m1 (in the previous equation), and plug in n-1 for m2 from the previous equation (no clue as to why...) and we get...

    (k+(n-1))! / (k!(n-1)!)
     
  2. jcsd
  3. Apr 12, 2006 #2
    Ok nevermind, just passed it.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook