# N! term in formula for combinations

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.

Related Set Theory, Logic, Probability, Statistics News on Phys.org
HallsofIvy
Homework Helper
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.

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.