Perms proof (1 Viewer)

[azureus88]

Prove that:

(i) (n+1)P(r) = (n)P(r) + r[(n+1)P(r)]

(ii) (n)P(r) = (n-2)P(r) + 2r[(n-2)P(r-1)] + r(r-1)[(n-2)P(r-2)]

i have no idea on how to get around this question. plz help. thanks!

 

[Timothy.Siu]

i) (n+1)P(r) = (n)P(r) + r[(n+1)P(r)]

LHS=(n+1)!/(n+1-r)!
RHS=n!/(n-r)!+r.(n+1)!/(n+1-r)!=n!(n-r+1)/(n-r+1)!+r.(n+1)!/(n+1-r)!=n!(n-r+1)+r.n!.(n+1)/(n+1-r)!=n!(n-r+1+rn+r)/(n+1-r)!=(n+1+rn)n!/(n+1-r)!
^^^
epic fail

*gives up*

 

[Trebla]

Prove that:

(i) (n+1)P(r) = (n)P(r) + r[(n+1)P(r)]

(ii) (n)P(r) = (n-2)P(r) + 2r[(n-2)P(r-1)] + r(r-1)[(n-2)P(r-2)]

i have no idea on how to get around this question. plz help. thanks!

I think the statement in (i) is incorrect. Subbing in a few numbers in a calculator shows they do not equal.

(ii) Use the definition: ⁿP_r = n! / (n - r)!
RHS = ^{n - 2}P_r + 2r.^{n - 2}P_{r - 1} + r(r - 1)^{n - 2}P_{r - 2}
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 2 - (r - 1))! + r(r - 1).(n - 2)! / (n - 2 - (r - 2))!
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 1 - r)! + r(r - 1).(n - 2)! / (n - r)!
= {(n - 2)!(n - 1 - r)(n - r) + 2r.(n - 2)!(n - r) + r(r - 1).(n - 2)!} / (n - r)!
= (n - 2)! {(n - 1 - r)(n - r) + 2r(n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n - 1 - r + 2r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r - 1) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r) - (n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {n² - r² - n + r + r² - r} / (n - r)!
= (n - 2)! {n² - n} / (n - r)!
= (n - 2)!(n - 1)n / (n - r)!
= n! / (n - r)!
= ⁿP_r
= LHS

 

[kaz1]

I think the statement in (i) is incorrect. Subbing in a few numbers in a calculator shows they do not equal.

(ii) Use the definition: ⁿP_r = n! / (n - r)!
RHS = ^{n - 2}P_r + 2r.^{n - 2}P_{r - 1} + r(r - 1)^{n - 2}P_{r - 2}
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 2 - (r - 1))! + r(r - 1).(n - 2)! / (n - 2 - (r - 2))!
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 1 - r)! + r(r - 1).(n - 2)! / (n - r)!
= {(n - 2)!(n - 1 - r)(n - r) + 2r.(n - 2)!(n - r) + r(r - 1).(n - 2)!} / (n - r)!
= (n - 2)! {(n - 1 - r)(n - r) + 2r(n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n - 1 - r + 2r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r - 1) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r) - (n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {n² - r² - n + r + r² - r} / (n - r)!
= (n - 2)! {n² - n} / (n - r)!
= (n - 2)!(n - 1)n / (n - r)!
= n! / (n - r)!
= ⁿP_r
= LHS

OMG! That's epic working out.

 

[azureus88]

I think the statement in (i) is incorrect. Subbing in a few numbers in a calculator shows they do not equal.

(ii) Use the definition: ⁿP_r = n! / (n - r)!
RHS = ^{n - 2}P_r + 2r.^{n - 2}P_{r - 1} + r(r - 1)^{n - 2}P_{r - 2}
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 2 - (r - 1))! + r(r - 1).(n - 2)! / (n - 2 - (r - 2))!
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 1 - r)! + r(r - 1).(n - 2)! / (n - r)!
= {(n - 2)!(n - 1 - r)(n - r) + 2r.(n - 2)!(n - r) + r(r - 1).(n - 2)!} / (n - r)!
= (n - 2)! {(n - 1 - r)(n - r) + 2r(n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n - 1 - r + 2r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r - 1) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r) - (n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {n² - r² - n + r + r² - r} / (n - r)!
= (n - 2)! {n² - n} / (n - r)!
= (n - 2)!(n - 1)n / (n - r)!
= n! / (n - r)!
= ⁿP_r
= LHS

yeh sorry, it was a typo. its meant to be (n+1)P(r) = (n)P(r) + r[(n)P(r-1)] but dont worry, i think i got it. btw, can u also explain how to calculate derangements of n objects. i dont get the cambridge explaination. thanks again.

 

[Trebla]

I'm not quite sure what you mean...

 

[azureus88]

I'm not quite sure what you mean...

ok the question is:

How many ways can n distinct objects be arranged so that none of the n objects appear in their orignial positions? For example, 4123 is a derangement of 1234 but 4132 isnt considered one because the 3 is in its original position.

 

[Timothy.Siu]

ok the question is:

How many ways can n distinct objects be arranged so that none of the n objects appear in their orignial positions? For example, 4123 is a derangement of 1234 but 4132 isnt considered one because the 3 is in its original position.

n ways?

 

[shaon0]

I think the statement in (i) is incorrect. Subbing in a few numbers in a calculator shows they do not equal.

(ii) Use the definition: ⁿP_r = n! / (n - r)!
RHS = ^{n - 2}P_r + 2r.^{n - 2}P_{r - 1} + r(r - 1)^{n - 2}P_{r - 2}
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 2 - (r - 1))! + r(r - 1).(n - 2)! / (n - 2 - (r - 2))!
= (n - 2)! / (n - 2 - r)! + 2r.(n - 2)! / (n - 1 - r)! + r(r - 1).(n - 2)! / (n - r)!
= {(n - 2)!(n - 1 - r)(n - r) + 2r.(n - 2)!(n - r) + r(r - 1).(n - 2)!} / (n - r)!
= (n - 2)! {(n - 1 - r)(n - r) + 2r(n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n - 1 - r + 2r) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r - 1) + r(r - 1)} / (n - r)!
= (n - 2)! {(n - r)(n + r) - (n - r) + r(r - 1)} / (n - r)!
= (n - 2)! {n² - r² - n + r + r² - r} / (n - r)!
= (n - 2)! {n² - n} / (n - r)!
= (n - 2)!(n - 1)n / (n - r)!
= n! / (n - r)!
= ⁿP_r
= LHS

You're really gun at maths. I'll give out that

 

[Timothy.Siu]

i dont think that question was hard, although i'm not denying trebla is really good at maths

 

[lolokay]

ok the question is:

How many ways can n distinct objects be arranged so that none of the n objects appear in their orignial positions? For example, 4123 is a derangement of 1234 but 4132 isnt considered one because the 3 is in its original position.

(can't confirm that this is actually correct)

if we have n objects, then n-1 can go in the first spot. now, say we consider the spot of the object that was just placed in the first spot. There are also n-1 objects that go in this spot. Now, we consider the spot of the object that took that place. There are now n-2 that can go in the spot. This continues, with one less object being able to go in each of the spots. This would give a value of (n-1)*(n-1)!.
BUT, when there are only 2 more objects to be arranged, one of these will be the initial object, and the other will be an object which hasn't had its spot picked yet. Since this object can only go in 1 of the 2 spots we can't multiply by the 2 in (n-1)!.
Therefore, the number of ways of arranging n distinct objects such that no object appears in its original position is (n-1)! *(n-1)/2.
(assuming n>2. If n = 1 or 2 then you don't get the final 2 objects so it's still just (n-1)!*(n-1) )