Hey there Sign in to join this conversationNew here? Join for free

Permutations algebra

Announcements Posted on
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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?
    • 1 follower
    Offline

    ReputationRep:
    (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
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (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?
    • 10 followers
    Offline

    ReputationRep:
    (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!
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (Original post by notnek)
    That's right and every factorial ends is a 1 so you have:
    Oh dear missed that.
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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)!}
    • 1 follower
    Offline

    ReputationRep:
    (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?
    • 10 followers
    Offline

    ReputationRep:
    (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
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (Original post by notnek)
    That's correct now you've edited it
    I got a bit excited then realised what I was doing:cool:
    • 1 follower
    Offline

    ReputationRep:
    (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
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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:
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    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:
    • 10 followers
    Offline

    ReputationRep:
    (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)!}
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (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
    • 10 followers
    Offline

    ReputationRep:
    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?
    • 10 followers
    Offline

    ReputationRep:
    (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))}
    • Thread Starter
    • 1 follower
    Offline

    ReputationRep:
    (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:
    • 10 followers
    Offline

    ReputationRep:
    (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.
    • 10 followers
    Offline

    ReputationRep:
    (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.

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?

    this is what you'll be called on TSR

  2. this can't be left blank
    this email is already registered. Forgotten your password?

    never shared and never spammed

  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide the button to the right to create your account

    Slide to join now Processing…

Updated: August 6, 2012
New on TSR

Your favourite film of the year?

For you personally what has been the best 2014 movie

Article updates
Reputation gems:
You get these gems as you gain rep from other members for making good contributions and giving helpful advice.