N! term in formula for combinations

  • Thread starter mmwave
  • Start date
211
2
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.
 

HallsofIvy

Science Advisor
Homework Helper
41,709
876
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.
 
211
2
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.
 

Related Threads for: N! term in formula for combinations

Replies
2
Views
2K
Replies
2
Views
2K
Replies
1
Views
660
Replies
2
Views
427
  • Posted
Replies
22
Views
22K
Replies
2
Views
4K
Replies
3
Views
5K
  • Posted
Replies
3
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top