# Permutations Proof

1. May 17, 2007

### Styx

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. May 17, 2007

### Dick

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
3. May 17, 2007

### Styx

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
4. May 17, 2007

### Dick

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

5. May 17, 2007

### Office_Shredder

Staff Emeritus
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?

6. May 17, 2007

### Dick

Brilliant!!!!!

7. May 17, 2007

### Styx

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
8. May 17, 2007

### Dick

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?

9. May 17, 2007

### Styx

I understand everything except how r/n becomes r-1

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

10. May 17, 2007

### Dick

You are doing some silly algebra. (n!/(n-r)!)/n=(n!/n)/(n-r)!. You don't divide (n-r)! by n also.

11. May 17, 2007

### Styx

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
12. May 17, 2007

### Dick

Yessssssssss

13. May 17, 2007

### Styx

Thanks Dick. It must hurt to help sometimes....

14. May 17, 2007

### Dick

It only hurts when they never get it.

15. Aug 18, 2010

### Hephzibah

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

16. Aug 21, 2010

### aq1q

now you should do a combinatorial (or counting in two ways) proof for fun