Permutation Recurrence Relation. Derivation?

[AvgStudent]

Hi, the recurrence relationship for permutation is stated in my textbook without showing how it came about. Hoping someone can enlighten me.
[math]P(n,r)=P(n-1,r)+rP(n-1,r-1)[/math]

 

[lex]

Note [imath]P(N,R)=\tfrac{N!}{(N-R)!}[/imath]


RHS = [imath]\tfrac{(n-1)!}{(n-r-1)!}+\tfrac{r(n-1)!}{(n-r)!}[/imath]

[imath]=\tfrac{(n-1)!}{(n-r)!}{((n-r) +r)}[/imath]

[imath]=\tfrac{n!}{(n-r)!}[/imath]

= LHS

 

[Harry_the_cat]

Do you know that \(\displaystyle P(n, r) =\frac{n!}{(n-r)!} \) ?

 

[Dr.Peterson]

Hi, the recurrence relationship for permutation is stated in my textbook without showing how it came about. Hoping someone can enlighten me.
[math]P(n,r)=P(n-1,r)+rP(n-1,r-1)[/math]

This can also be demonstrated in terms of the meaning of permutations, rather than the formula.

P(n,r) is the number of ways to permute r of n objects. Consider one of those objects, perhaps the last one in the given list. Call it X. Each permutation either includes X, or does not. These are mutually exclusive.

Each permutation not including X is a permutation of r of the other n-1 objects, so there are P(n-1,r) of them.

Each permutation including X places X in one of the r locations, and fills in the remaining r-1 places from the remaining n-1 objects, so this can be done in rP(n-1,r-1) ways.

 

[AvgStudent]

Do you know that \(\displaystyle P(n, r) =\frac{n!}{(n-r)!} \) ?

Yes, I know that, at least.

Note [imath]P(N,R)=\tfrac{N!}{(N-R)!}[/imath]


RHS = [imath]\tfrac{(n-1)!}{(n-r-1)!}+\tfrac{r(n-1)!}{(n-r)!}[/imath]

[imath]=\tfrac{(n-1)!}{(n-r)!}{((n-r) +r)}[/imath]

[imath]=\tfrac{n!}{(n-r)!}[/imath]

= LHS

Thank you, Lex. Initially, I was more interested in how they go from the LHS to the RHS, but from seeing your work, they rewrite n=n+r-r and apply simple algebra to obtain the expression on the RHS.

This can also be demonstrated in terms of the meaning of permutations, rather than the formula.

P(n,r) is the number of ways to permute r of n objects. Consider one of those objects, perhaps the last one in the given list. Call it X. Each permutation either includes X, or does not. These are mutually exclusive.

Each permutation not including X is a permutation of r of the other n-1 objects, so there are P(n-1,r) of them.

Each permutation including X places X in one of the r locations, and fills in the remaining r-1 places from the remaining n-1 objects, so this can be done in rP(n-1,r-1) ways.

You've answered my follow up question, which was "what's the point of doing so?". That's a great interpretation by the Rule of Sum.

Thanks all.

 

[Steven G]

What is the point of this identity.
1) It makes total sense as Dr Peterson stated.
2) That identity stares you in the face when you write out pascals triangle. Confirm this!