The Student Room Group

Permutations algebra

Hi, how does this work,

nPk=n(n1)...(nk+1)=n(n1)...(nk+1)(nk)!(nk)!=n!(nk)!\displaystyle ^nP_k= n(n-1)...(n-k+1)\\ \\ =\frac{n(n-1)...(n-k+1)(n-k)!}{(n-k)!} \\ \\ = \frac{n!}{(n-k)!}

How does the third line occur?

And that may be the key to me getting the next thing I cannot follow.


nCk=nPkk!=n(n1)...(nk+1)k!sonCk=n!(nk)!k!\displaystyle ^nC_k=\frac{^nP_k}{k!}=\frac{n(n-1)...(n-k+1)}{k!} \\ \\ \mathrm{so} \\ \\ ^nC_k=\frac{n!}{(n-k)!k!}

So it can be seen (though not by me:redface:) that

nCk+1\displaystyle ^nC_{k+1}

can be obtained by multiplying nCk\displaystyle ^nC_k by the fraction

nkk+1\displaystyle \frac{n-k}{k+1}

Don't get it:rolleyes:

Also what part of the A-level syllabus is permutations and combinations?
(edited 11 years ago)

Scroll to see replies

Original post by SubAtomic
Hi, how does this work,

nPk=n(n1)...(nk+1)=n(n1)...(nk+1)(nk)!(nk)!=n!(nk)!\displaystyle ^nP_k= n(n-1)...(n-k+1)\\ \\ =\frac{n(n-1)...(n-k+1)(n-k)!}{(n-k)!} \\ \\ = \frac{n!}{(n-k)!}

How does the third line occur?


Expand out the (n-k)! on the top too - then you just have a product from n to 1, which is n!

Original post by SubAtomic
And that may be the key to me getting the next thing I cannot follow.


nCk=nPkk!=n(n1)...(nk+1)k!sonCk=n!(nk)!k!\displaystyle ^nC_k=\frac{^nP_k}{k!}=\frac{n(n-1)...(n-k+1)}{k!} \\ \\ \mathrm{so} \\ \\ ^nC_k=\frac{n!}{(n-k)!k!}



Just replace the nPk^nP_k in the numerator by the result of the first part, then remember that

abc=abc \frac{\frac{a}{b}}{c} = \frac{a}{bc}

Original post by SubAtomic
So it can be seen (though not by me:redface:) that

nCk+1\displaystyle ^nC_{k+1}

can be obtained by multiplying nCk\displaystyle ^nC_k by the fraction

nkk+1\displaystyle \frac{n-k}{k+1}

Don't get it:rolleyes:


Replace k by k+1 in the formula for ^nC_{k}. Then see if you can work out why it's true (if not, post the result of this substitution and any working you do :smile: )

Original post by SubAtomic

Also what part of the A-level syllabus is permutations and combinations?


When I did it, it was in S1 :smile:
(edited 11 years ago)
Reply 2
Original post by dantheman1261
Expand out the (n-k)! on the top too


No idea what to do here, at least I don't think I do, would it be


(nk)!(nk)×(nk1)...?\displaystyle (n-k)! \equiv (n-k) \times (n-k-1)...?

Nope no idea:redface:

Never seen what to do and don't think I have an example in my book.

Maybe I am just supposed to take it for what it is and not try to derive it myself?
(edited 11 years ago)
Reply 3
Original post by SubAtomic
No idea what to do here, at least I don't think I do, would it be


(nk)!(nk)×(nk1)...?\displaystyle (n-k)! \equiv (n-k) \times (n-k-1)...?

That's right and every factorial ends is a 1 so you have:

(nk)!(nk)×(nk1)××1\displaystyle (n-k)! \equiv (n-k) \times (n-k-1)\times\cdots \times 1

So you have on the numerator:

n×(n1)××(nk)×(nk1)××1\displaystyle n \times (n-1) \times \cdots \times (n-k) \times (n-k-1) \times \cdots \times 1

The (nk)(n-k) and (nk1)(n-k-1) are just consecutive numbers in between 1 and n so this is equal to

n×(n1)××1=n!\displaystyle n \times (n-1) \times \cdots \times 1 = n!
(edited 11 years ago)
Reply 4
Original post by notnek
That's right and every factorial ends is a 1 so you have:


Oh dear:colondollar: missed that.
Reply 5
So if I were to rewrite it like this it would make more sense to me, but correct me if I am wrong, I think I am, yep wrong way round. Is it right now?


nPk=n×(n1)×...×(nk+1)×(nk)×(nk1)×...×1(nk)!\displaystyle ^nP_k=\dfrac{n \times (n-1) \times ... \times (n-k+1) \times (n-k) \times (n-k-1) \times ... \times 1}{(n-k)!}
(edited 11 years ago)
Original post by SubAtomic
So if I were to rewrite it like this it would make more sense to me, but correct me if I am wrong, I think I am, yep wrong way round. Is it right now?


nPk=n×(n1)×...×(nk+1)×(nk)×(nk1)×...×1(nk)!\displaystyle ^nP_k=\dfrac{n \times (n-1) \times ... \times (n-k+1) \times (n-k) \times (n-k-1) \times ... \times 1}{(n-k)!}


That's right. Do you see how it works? What about the other parts of the question?
Reply 7
Original post by SubAtomic
So if I were to rewrite it like this it would make more sense to me, but correct me if I am wrong, I think I am, yep wrong way round. Is it right now?


nPk=n×(n1)×...×(nk+1)×(nk)×(nk1)×...×1(nk)!\displaystyle ^nP_k=\dfrac{n \times (n-1) \times ... \times (n-k+1) \times (n-k) \times (n-k-1) \times ... \times 1}{(n-k)!}

That's correct now you've edited it :smile:
Reply 8
Dan yes I think so, so basically the second part I am just multiplying top and bottom by (n-k)! to get the denom like it is? If so I think I see the nCk now:smile:
(edited 11 years ago)
Reply 9
Original post by notnek
That's correct now you've edited it :smile:


I got a bit excited then realised what I was doing:cool:
Original post by SubAtomic

Dan, yes I think so, so basically the second part I am just multiplying top and bottom by (n-k)! to get the denom like it is? If so I think I see the nCk now:smile:


Yeah that's right :smile: (what I wrote was more unnecessarily convoluted than that). That should lead you on nicely to the last part
Reply 11
So here goes but not too sure what I am doing


nCk×nkk+1=(nk)n!(k+1)k!\displaystyle ^nC_k \times \frac{n-k}{k+1}=\frac{(n-k)n!}{(k+1)k!}

So if I replace the k with k+1 in the nCk^nC_k formula I end up with

nCk+1=n×(n1)×...×(nk+2)(k+1)!\displaystyle ^nC_{k+1} = \dfrac{n\times (n-1) \times ... \times (n-k+2)}{(k+1)!}


(nk)(n×(n1)×...×(nk+1))(k+1)k!\displaystyle \dfrac {(n-k)\cdot(n \times (n-1) \times ... \times (n-k+1))}{(k+1)k!}


Need to dwell, much appreciated guys:cool:
(edited 11 years ago)
Reply 12
There is something similar covered in C2, but I can get answers using the formula just cannot quite work the formula out for myself. Anywhere I can see a proof of what I am trying to work out in the above post? Think I have lost the plot :dunce:
(edited 11 years ago)
Reply 13
Original post by SubAtomic
So here goes but not too sure what I am doing


nCk×nkk+1=(nk)n!(k+1)k!\displaystyle ^nC_k \times \frac{n-k}{k+1}=\frac{(n-k)n!}{(k+1)k!}

So if I replace the k with k+1 in the nCk^nC_k formula I end up with

nCk+1=n×(n1)×...×(nk+2)(k+1)!\displaystyle ^nC_{k+1} = \dfrac{n\times (n-1) \times ... \times (n-k+2)}{(k+1)!}


(nk)(n×(n1)×...×(nk+1))(k+1)k!\displaystyle \dfrac {(n-k)\cdot(n \times (n-1) \times ... \times (n-k+1))}{(k+1)k!}


Need to dwell, much appreciated guys:cool:

You have said in your first line that

nCk=n!k!\displaystyle ^nC_k =\frac{n!}{k!}

but this is not true.

Try doing the same thing using the correct result:

nCk=n!k!(nk)!\displaystyle ^nC_k =\frac{n!}{k!(n-k)!}
Reply 14
Original post by notnek
You have said in your first line that

nCk=n!k!\displaystyle ^nC_k =\frac{n!}{k!}

but this is not true.

Try doing the same thing using the correct result:

nCk=n!k!(nk)!\displaystyle ^nC_k =\frac{n!}{k!(n-k)!}


Think it is the book that is sending me on a tangent, the book says, it can be seen from equation (5.6) that nCk+1^nC_{k+1} can be obtained by multiplying
nCk^nC_k by the fraction nkk+1\frac{n-k}{k+1} equation 5.6 is given as nPkk!=n(n1)...(nk+1)k!\displaystyle\frac{^nP_k}{k!}= \frac{n(n-1)...(n-k+1)}{k!}

So will try it your way now, tried it that way first but it but backtracked because of the book:rolleyes:

I end up with

(nk)n!(k+1)(nk)!k!\displaystyle\frac{(n-k)n!}{(k+1)(n-k)!k!}

Can I cancel the (n-k) or does the factorial stop this being possible?

Would I end up with

n!(k+1)!k!\displaystyle\frac{n!}{(k+1)!k!}

Maybe it is because I was taking
Unparseable latex formula:

\displaystle ^nP_k

as n(n1)...(nk+1)\displaystyle n(n-1)...(n-k+1) rather than n!(nk)!\displaystyle \frac{n!}{(n-k)!} but the book shows it as the former:s-smilie:
(edited 11 years ago)
Reply 15
You can't just "cancel" (nk)(n-k) and (nk)!(n-k)! since they're different things.

But you have (nk)(n-k) on the top and (nk)(n(k+1))(n(k+2))1(n-k)(n-(k+1))(n-(k+2))\cdots 1 on the bottom so there is a factor of (nk)(n-k) that you can cancel. So

(nk)n!(k+1)(nk)!k!=(nk)n!(k+1)(nk)(n(k+1))(n(k+2))1×k!\displaystyle \frac{(n-k)n!}{(k+1)(n-k)!k!}= \frac{(n-k)n!}{(k+1)(n-k)(n-(k+1))(n-(k+2))\cdots 1 \times k!}


=n!(k+1)(n(k+1))(n(k+2))1×k!=n!(k+1)(n(k+1))!×k!\displaystyle = \frac{n!}{(k+1)(n-(k+1))(n-(k+2))\cdots 1 \times k!} = \frac{n!}{(k+1)(n-(k+1))! \times k!}


Now notice that (k+1)×k!(k+1) \times k! is equal to (k+1)!(k+1)! in the same way that e.g. 5x4!=5! or 8x7!=8!.

Does it make sense now?
(edited 11 years ago)
Reply 16
Original post by SubAtomic

Maybe it is because I was taking
Unparseable latex formula:

\displaystle ^nP_k

as n(n1)...(nk+1)\displaystyle n(n-1)...(n-k+1) rather than n!(nk)!\displaystyle \frac{n!}{(n-k)!} but the book shows it as the former:s-smilie:

They are equal to each other

n!(nk)!=n(n1)(n(k1))(nk)(n(k+1))1(nk)(n(k+1))1\displaystyle \frac{n!}{(n-k)!} = \frac{n(n-1)\cdots (n-(k-1))(n-k)(n-(k+1))\cdots 1}{(n-k)(n-(k+1))\cdots 1}

Unparseable latex formula:

\displaystyle = n(n-1)\cdots (n-(k-1))}

Reply 17
Original post by notnek
You can't just "cancel" (nk)(n-k) and (nk)!(n-k)! since they're different things.


Had my suspicions about this.

Original post by notnek
But you have (nk)(n-k) on the top and (nk)(n(k+1))(n(k+2))1(n-k)(n-(k+1))(n-(k+2))\cdots 1 on the bottom so there is a factor of (nk)(n-k) that you can cancel. So

(nk)n!(k+1)(nk)!k!=(nk)n!(k+1)(nk)(n(k+1))(n(k+2))1×k!\displaystyle \frac{(n-k)n!}{(k+1)(n-k)!k!}= \frac{(n-k)n!}{(k+1)(n-k)(n-(k+1))(n-(k+2))\cdots 1 \times k!}


=n!(k+1)(n(k+1))(n(k+2))1×k!=n!(k+1)(n(k+1))!×k!\displaystyle = \frac{n!}{(k+1)(n-(k+1))(n-(k+2))\cdots 1 \times k!} = \frac{n!}{(k+1)(n-(k+1))! \times k!}


Now notice that (k+1)×k!(k+1) \times k! is equal to (k+1)!(k+1)! in the same way that e.g. 5x4!=5! or 8x7!=8!.

Does it make sense now?


Thank you, makes complete sense now:smile: So I should have expanded the factorial on the bottom to do it, and also used the complete result for nCk\displaystyle^nC_k rather than (5.6)?

Original post by notnek
They are equal to each other

n!(nk)!=n(n1)(n(k1))(nk)(n(k+1))1(nk)(n(k+1))1\displaystyle \frac{n!}{(n-k)!} = \frac{n(n-1)\cdots (n-(k-1))(n-k)(n-(k+1))\cdots 1}{(n-k)(n-(k+1))\cdots 1}

Unparseable latex formula:

\displaystyle = n(n-1)\cdots (n-(k-1))}



Yep it didn't help my seeing what was going on though:s-smilie: I need to see everything to understand it sometimes.

Also the book didn't ask this of me so was it a good idea for me to look into it or should I sometimes just take a formula for what it is?

Had no problem using the formula but just didn't get the steps to acquire the formula:rolleyes:
(edited 11 years ago)
Reply 18
Original post by SubAtomic

Thank you, makes complete sense now:smile: So I should have expanded the factorial on the bottom to do it, and also used the complete result for nCk\displaystyle^nC_k rather than (5.6)?



Yep it didn't help my seeing what was going on though:s-smilie: I need to see everything to understand it sometimes.

Also the book didn't ask this of me so was it a good idea for me to look into it or should I sometimes just take a formula for what it is?

I'm finding it hard to see how the book is explaining things without seeing the book. The equation doesn't seem relevant but it might be if I could see all of the working.

Which book is it? I may be able to find the pages online.
Reply 19
Original post by SubAtomic
Attached pics of a few pages, probably me being a moron:s-smilie:

Binomial theorem, permutations and combinations is covered in 6 pages, don't know if that was enough for the first time I have seen it.

I got confused because you didn't write down the nCk=\displaystyle^n C_k = part when posting eqn (5.6) although I probably should've noticed that they were equal.


So if we use (5.6):

nCk=n(n1)(n(k1))k!\displaystyle^n C_k = \frac{n(n-1)\cdots (n-(k-1))}{k!}

then

nCk+1=n(n1)(nk))(k+1)!\displaystyle^n C_{k+1} = \frac{n(n-1)\cdots (n-k))}{(k+1)!}

and you can write this in a different way:

=n(n1)(n(k1))(nk)k!×(k+1)=n(n1)(n(k1))k!×nkk+1=\displaystyle \frac{n(n-1)\cdots (n-(k-1))(n-k)}{k!\times (k+1)} = \frac{n(n-1)\cdots (n-(k-1))}{k!} \times \frac{n-k}{k+1}


Also if you haven't already, you should look at the example they have given with k=2. That might make it more clear to you.

Quick Reply

Latest