Permutation Proof

S

scar3krow

New member
Joined
Jul 2, 2019
Messages
1
Sorry if this is the wrong section, not exactly sure where permutations fit in.

The question is asking to prove that:
P(n-1,r) = P(n-2,r) + r( P(n-2,r-1) )

I am unsure how to go about this, I can do the basic proof of how a permutation equals its factorial components, but that doesn't seem to be getting me anywhere with this question. Quite confused as I cannot figure out how on earth you would factor out an 'r' in front of a permutation. Any help appreciated.
Thanks!
 
You just need to get your hands a bit dirty.
1st find P(n-2,r), then find P(n-2,r-1) and multiply this last result by r. Add the two the usual way--find a common denominator and then simplify.
Please do this and show us your work and we'll proceed from there. If you get stuck then show us your work and we'll help you.

BTW, the r is already factored out. P(n,r) is some number and r is some number so you just multiply the two numbers. Why is that bothering you?
 
This sort of proof can be done either algebraically, using the formula for permutations as Jomo has suggested, or by a "combinatorial proof", using the meaning of permutations.

To do that, observe that the LHS (left-hand side) counts the ways to arrange r out of a set of n-1 objects. Think about how to count them by making two sets of arrangements, one in P(n-2,r) ways, and the other in r times P(n-2,r-1) ways. It's not hard to do. I'd start by thinking of P(n-2,r) as the number of ways to arrange r from the first n-2 of the objects, omitting the last one. Then the second term should be the number of ways to arrange that last one together with others.
 
Dr.Peterson said:
This sort of proof can be done either algebraically, using the formula for permutations as Jomo has suggested, or by a "combinatorial proof", using the meaning of permutations.

To do that, observe that the LHS (left-hand side) counts the ways to arrange r out of a set of n-1 objects. Think about how to count them by making two sets of arrangements, one in P(n-2,r) ways, and the other in r times P(n-2,r-1) ways. It's not hard to do. I'd start by thinking of P(n-2,r) as the number of ways to arrange r from the first n-2 of the objects, omitting the last one. Then the second term should be the number of ways to arrange that last one together with others.
Click to expand...
Prof Peterson, I 100% agree with you that one should see why the identity is correct. For the record after the OP did the proof algebraically I would have noted why this is obvious. My question to you, and this is just about your opinion , js would you mark a student correct if they just wrote why this is true, as you did, but did not do the algebra?

I'm just curious and would like others to give their opinion

I'll start off with my opinion. I would be glad that the student saw the reason. I would have told the student she/he should have shown the algebra but would have given full credit for seeing the relationship.
 
BTW, this should have been posted in the probability forum
 
Jomo said:
Prof Peterson, I 100% agree with you that one should see why the identity is correct. For the record after the OP did the proof algebraically I would have noted why this is obvious. My question to you, and this is just about your opinion , is would you mark a student correct if they just wrote why this is true, as you did, but did not do the algebra?

I'm just curious and would like others to give their opinion.

I'll start off with my opinion. I would be glad that the student saw the reason. I would have told the student she/he should have shown the algebra but would have given full credit for seeing the relationship.
Click to expand...
They are two different, equally valid, approaches to a proof. The combinatorial proof is more than merely "seeing why it's obvious", just as the algebraic proof is more than merely "moving letters around". (See the Wikipedia page I linked to.)

I would expect the assignment to have stated (or implied from context) which method was intended to be used; for example, if they haven't seen combinatorial proofs (or haven't seen the formulas) then it would be clear what was intended. (If under those conditions a student gave the "other" kind of proof, I would probably be amazed and give credit!) But without any indication, I see no reason to reject either approach. I would want to teach both, and expect students to be able to do both.

In this case, I can't say that I know which was asked for, though the student appears to be thinking algebraically. That could be a result of not paying attention in class!
 
As someone who is not a professional mathematician, I am guessing that the algebraic approach is what is expected. The OP is not aware that combinatorics is usually treated in conjunction with probability. Moreover, the OP posted a problem in discrete mathematics in the calculus forum! I greatly doubt that the OP has a clue how to do a combinatoric proof. But I also guess that the OP knows elementary algebra.
 
You must log in or register to reply here.
Top