Permutations algebra

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
TSR launches Learn Together! - Our new subscription to help improve your learning 16-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
Search Thread
Advanced Search
Sign in to Reply
  1. SubAtomic's Avatar
    1 05-08-2012  18:14
    • Exalted and Worshipped Member
    • Posts: 1,316
    Permutations algebra
    Hi, how does this work,

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


    \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) that

    \displaystyle ^nC_{k+1}

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

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

    Don't get it:rolleyes:

    Also what part of the A-level syllabus is permutations and combinations?
    Last edited by SubAtomic; 12-08-2012 at 00:35.
  2. dantheman1261's Avatar
    2 05-08-2012  18:47
    • Full Member
    • Posts: 105
    Re: Permutations algebra
    (Original post by SubAtomic)
    Hi, how does this work,

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


    \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 ^nP_k in the numerator by the result of the first part, then remember that

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

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

    \displaystyle ^nC_{k+1}

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

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

    (Original post by SubAtomic)
    Also what part of the A-level syllabus is permutations and combinations?
    When I did it, it was in S1
    Last edited by dantheman1261; 05-08-2012 at 18:48.
    Post rating:
    1
  3. SubAtomic's Avatar
    3 05-08-2012  19:12
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    (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


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

    Nope no idea

    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?
    Last edited by SubAtomic; 05-08-2012 at 19:20.
  4. notnek's Avatar
    4 05-08-2012  19:20
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (Original post by SubAtomic)
    No idea what to do here, at least I don't think I do, would it be


    \displaystyle (n-k)! \equiv (n-k) \times (n-k-1)...?
    That's right and every factorial ends is a 1 so you have:

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

    So you have on the numerator:

    \displaystyle n \times (n-1) \times \cdots \times (n-k) \times (n-k-1) \times \cdots \times 1

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

    \displaystyle n \times (n-1) \times \cdots \times 1 = n!
    Last edited by notnek; 05-08-2012 at 19:22.
    Post rating:
    1
  5. SubAtomic's Avatar
    5 05-08-2012  19:21
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    (Original post by notnek)
    That's right and every factorial ends is a 1 so you have:
    Oh dear missed that.
  6. SubAtomic's Avatar
    6 05-08-2012  19:36
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    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?


    \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)!}
    Last edited by SubAtomic; 05-08-2012 at 19:41.
  7. dantheman1261's Avatar
    7 05-08-2012  19:43
    • Full Member
    • Posts: 105
    Re: Permutations algebra
    (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?


    \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?
  8. notnek's Avatar
    8 05-08-2012  19:44
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (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?


    \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
  9. SubAtomic's Avatar
    9 05-08-2012  19:56
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    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
    Last edited by SubAtomic; 05-08-2012 at 20:14.
  10. SubAtomic's Avatar
    10 05-08-2012  19:58
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    (Original post by notnek)
    That's correct now you've edited it
    I got a bit excited then realised what I was doing:cool:
  11. dantheman1261's Avatar
    11 05-08-2012  20:02
    • Full Member
    • Posts: 105
    Re: Permutations algebra
    (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
    Yeah that's right (what I wrote was more unnecessarily convoluted than that). That should lead you on nicely to the last part
  12. SubAtomic's Avatar
    12 05-08-2012  20:09
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    So here goes but not too sure what I am doing


    \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 ^nC_k formula I end up with

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


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


    Need to dwell, much appreciated guys:cool:
    Last edited by SubAtomic; 05-08-2012 at 20:58.
  13. SubAtomic's Avatar
    13 05-08-2012  23:35
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    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:
    Last edited by SubAtomic; 05-08-2012 at 23:36.
  14. notnek's Avatar
    14 06-08-2012  06:43
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (Original post by SubAtomic)
    So here goes but not too sure what I am doing


    \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 ^nC_k formula I end up with

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


    \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

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

    but this is not true.

    Try doing the same thing using the correct result:

    \displaystyle ^nC_k =\frac{n!}{k!(n-k)!}
  15. SubAtomic's Avatar
    15 06-08-2012  12:29
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    (Original post by notnek)
    You have said in your first line that

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

    but this is not true.

    Try doing the same thing using the correct result:

    \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 ^nC_{k+1} can be obtained by multiplying
    ^nC_k by the fraction \frac{n-k}{k+1} equation 5.6 is given as \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

    \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

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

    Maybe it is because I was taking \displaystle ^nP_k as \displaystyle n(n-1)...(n-k+1) rather than \displaystyle \frac{n!}{(n-k)!} but the book shows it as the former
    Last edited by SubAtomic; 06-08-2012 at 12:47.
  16. notnek's Avatar
    16 06-08-2012  12:48
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    You can't just "cancel" (n-k) and (n-k)! since they're different things.

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

    \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!}


    \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) \times k! is equal to (k+1)! in the same way that e.g. 5x4!=5! or 8x7!=8!.

    Does it make sense now?
    Last edited by notnek; 06-08-2012 at 12:50.
  17. notnek's Avatar
    17 06-08-2012  12:53
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (Original post by SubAtomic)
    Maybe it is because I was taking \displaystle ^nP_k as \displaystyle n(n-1)...(n-k+1) rather than \displaystyle \frac{n!}{(n-k)!} but the book shows it as the former
    They are equal to each other

    \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}

    \displaystyle = n(n-1)\cdots (n-(k-1))}
  18. SubAtomic's Avatar
    18 06-08-2012  13:04
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Permutations algebra
    (Original post by notnek)
    You can't just "cancel" (n-k) and (n-k)! since they're different things.
    Had my suspicions about this.

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

    \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!}


    \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) \times k! is equal to (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 So I should have expanded the factorial on the bottom to do it, and also used the complete result for \displaystyle^nC_k rather than (5.6)?

    (Original post by notnek)
    They are equal to each other

    \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}

    \displaystyle = n(n-1)\cdots (n-(k-1))}
    Yep it didn't help my seeing what was going on though 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:
    Last edited by SubAtomic; 06-08-2012 at 13:13.
  19. notnek's Avatar
    19 06-08-2012  13:15
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (Original post by SubAtomic)
    Thank you, makes complete sense now So I should have expanded the factorial on the bottom to do it, and also used the complete result for \displaystyle^nC_k rather than (5.6)?



    Yep it didn't help my seeing what was going on though 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.
  20. notnek's Avatar
    20 06-08-2012  14:07
    • TSR Demigod
    • Location: Bangkok, Thailand
    Re: Permutations algebra
    (Original post by SubAtomic)
    Attached pics of a few pages, probably me being a moron

    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 \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):

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

    then

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

    and you can write this in a different way:

    =\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.
Sign in to Reply
Search Thread
Advanced Search
Share this discussion:  
Useful resources

Articles:

Study Help rules and posting guidelinesStudy Help Member of the Month nominationsGuide to MathematicsMathematics resourcesMathematics websitesMathematics revision notes in the TSR wikiCambridge Assessment admissions tests (including STEP)How to use LaTeXCareers in Mathematics

Useful Dates:

Quick Link:

Unanswered Maths Threads

Groups associated with this forum:

View associated groups
Article updates
Moderators

We have a brilliant team of more than 60 volunteers looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is moderated by:

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22

Registered Office: International House, Queens Road, Brighton, BN1 3XE

Shortcuts

Get Started

TSR Group

Using TSR

Info

Connect with TSR

Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.