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: Permutations Proof

  1. May 17, 2007 #1
    Prove that P(n,r) / n = P(n-1,r-1)

    I know that it is right but I have having a hard time coming up with a step by step solution.

    Is P(n-1,r-1) the same as (n-1)!
     
  2. jcsd
  3. May 17, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Take a concrete example. P(7,3)=7*6*5, P(6,2)=6*5. So is P(7,3)/7=P(6,2)? Yes. Is P(6,2)=6!? NO. What's the general formula for P(n,r)?
     
    Last edited: May 17, 2007
  4. May 17, 2007 #3
    I know that the statement is true but I don't think I can use a specific example as that would be conjecture and not a proof.

    P(n,r)= n!/(n-r)! = n x (n-1) x (n-2) x .... x (n - r + 1)
     
    Last edited: May 17, 2007
  5. May 17, 2007 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    P(n-1,r-1)=(n-1)! is false. If P(n,r)=n!/(n-r)!, what's the correct formula for P(n-1,r-1)?
     
  6. May 17, 2007 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No....
    P(n,r)/n= n!/(n-r)!/n = n x (n-1) x (n-2) x .... x (n - r + 1)/n =
    (n-1) x (n-2) x .... x (n - r + 1) = (n-1) x (n-2) x .... x (n - (r - 1) )

    Can you solve it from there?
     
  7. May 17, 2007 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Brilliant!!!!!
     
  8. May 17, 2007 #7
    Ok, how about this:

    P(n,r)/n = n!/(n-r)!/n = (n-1)!/(n-r)! = P(n-1, r-1)

    EDIT:

    Actually, wouldn't (n-1)!/(n-r)! be P(n-1, r)?

    6!/3! = 120, 120/6 = 20
    5!/3! = 20
    while 5!/2! = 60
     
    Last edited: May 17, 2007
  9. May 17, 2007 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I thought you had it. P(n-1,r-1)=(n-1)!/((n-1)-(r-1))!, right? Just substitute n-1 for n and r-1 for r in P(n,r). Can you simplify that expression slightly?
     
  10. May 17, 2007 #9
    I understand everything except how r/n becomes r-1

    n!/n = (n-1)!
    (n-r)!/n = ((n-1)-(r/n))!
     
  11. May 17, 2007 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You are doing some silly algebra. (n!/(n-r)!)/n=(n!/n)/(n-r)!. You don't divide (n-r)! by n also.
     
  12. May 17, 2007 #11
    Ok, so I was right before.

    n!/(n-r)!/n = (n-1)!/(n-r)!

    but (n-r)! is equal to ((n-1)-(r-1))!

    therefore, n!/(n-r)!/n = (n-1)!/((n-1)-(r-1))!

    (n-1)!/((n-1)-(r-1)) = P(n-1, r-1)

    therefore, n!/(n-r)!/n = P(n-1, r-1)

    You have no idea how much trouble my algebra gets me into. Here I am doing grade 12 Geometry and I should probably be reviewing my grade 9 algebra instead...
     
    Last edited: May 17, 2007
  13. May 17, 2007 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yessssssssss
     
  14. May 17, 2007 #13
    Thanks Dick. It must hurt to help sometimes....
     
  15. May 17, 2007 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It only hurts when they never get it.
     
  16. Aug 18, 2010 #15
    L.H.S
    p(n,r)/n
    = n!/n(n-r)!
    = n (n-1)!/n(n-r)!
    = (n-1)!/(n-r)!
    = P (n-1,r-1)
    = R.H.S
     
  17. Aug 21, 2010 #16
    now you should do a combinatorial (or counting in two ways) proof for fun
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook