1. Not finding help here? Sign up for a free 30min 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!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations Proof
  1. Counting permutations (Replies: 6)

  2. Permutation proof (Replies: 7)

Loading...