How Does P(n,r) / n Relate to P(n-1,r-1) in Combinatorial Proofs?

[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)!

 

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

 

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

 

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

 

[Office_Shredder]

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

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?

 

[Dick]

Brilliant!

 

[Styx]

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

 

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

 

[Styx]

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

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

 

[Dick]

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

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

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

 

[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 are doing some silly algebra

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...

 

[Dick]

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...

Yessssssssss

 

[Styx]

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

 

[Dick]

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

It only hurts when they never get it.

 

[Hephzibah]

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

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

 

[aq1q]

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