Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N! term in formula for combinations

  1. Sep 21, 2003 #1
    I once read a very good explanation for the n! factor in the combinations formula but I can't find it. Can someone state the reason for it clearly please.

    ( N) = N!/n!/(N-n)!
    ( n)

    The N!/(N-n)! comes about because there are that many ways to choose n things from N. N for the first, N-1 for the second, ... N-n+1 for the nth. So far so good.

    There is a clear explanation for why this has 'double counted' and the n! term fixes it up.
     
  2. jcsd
  3. Sep 22, 2003 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The number of "permutations" of N things, taken i at a time, and sometimes called NPi is N!/(N-i)!. That's true because you have N choices for the first thing, then N-1 choices for the second, etc. until you have taken i of them. That's N(N-1)(N-2)...(N-i+1)) That's a total of i factors and the last of them is
    (N-i)+1. One way to write that is to start with N! and "cancel" those below N-i+1 by dividing by (N-1)!.

    Look at an example. If we had 4 things: {a, b, c, d} and asked for "all permutations of those 4 things, take 2 at a time" we would be seeking {a,b}, {a,c}, {a,d} (I've chosen a first and then each of the other 3 second), {b,a}, {b,c}, {b,d} (choose b first), {c,a}, {c,b}, {c,d} (get the idea?), {d,a}, {d,b}, {d,c}.
    A total of 4*3= 4!/2!= 4!/(4-2)!= 4P2 permutations.

    That's the part you have.

    Now, to get "combinations" where order is not important:

    The 12 permutations we have include both {a,b} and {b,a}, {a,c} and {c,a}, etc. In fact every pair is "duplicated" in reverse order. That's because there are 2!= 2 ways of permuting 2 things.
    If we don't want to count permutations as different combinations, we need to divide by 2: there are 6= (4P2)/2
    = (4!/2!)/2!= 4!/((4-2)!2!)= 4C2.

    If we want all combinations of N things taken i at a time, we can calculate, as above, that there are N!/(N-i)! permutations. Since there are i! ways to permute the same i things, to not count permutations of the same things as different combinations, we need to multiply by i!: N!/((N-i)!i!)= NCi.
     
  4. Sep 24, 2003 #3
    Thanks! That was it, we have ab and ba so divide by 2. If n things divide by n!

    I knew it was not as complicated as my statistical physics teacher made it sound.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: N! term in formula for combinations
Loading...