Saturday, June 1, 2013

The binomial coefficient - an explanation for kids

The binomial coefficient (n choose k) is very simple to understand, if explained by means of an example.

For instance if I have 52 cards and want to count all possible ways to choose two cards from the deck, I reason like this: the first card I can obviously
choose in 52 ways. For each choice of the first card I have 52-1=51
ways to choose the second one, so in total there are 52*51=2652 ways, if I
care about order. If I do not, I have to divide by two, because 2 are
all the possible ways to permute each set of two cards. Therefore I
have 52*51/2=1326. This is the value of "52 choose 2".

Now, what is "52 choose 3"? Same reasoning: 52*51*50 gives me all
combinations, also those differing for order only. If I want to consider
all combinations having the same three cards but in different order as
the same combination, I have to divide that figure by the number of these
Now, in how many ways can two elements permute? 2 ways (AB, BA). And 3
elements? It's 3*2 ways: ABC, ACB, BAC, BCA, CAB, CBA. You see I put A
as the first element, then permuted the remaining two (B and C). Then I put B as the first and permuted the other two (A and B)... So 52 choose 3 is

What is n choose k? It's n*(n-1)*..*(n-k+1)/(k*(k-1)*...*2)
It looks like a complicated formula, but you can see it works for n=52 and
k=2,3 or any other value of n and k. Well, not really any. Obviously, for this to make sense n-k+1 must be non-negative and non-zero, that is n-k+1>0 or n>k-1. Since k and n are integer, n>k-1 means n>=k (e.g. if k=5, n>5-1 or n>4 means n>=5, given that n is also integer). The formula does not make sense if n
Mathematicians call k*(k-1)*...*2*1 (I have added a harmless *1) the
"factorial of k". It's just a specific word for the product of an
integer by all the integers that come before it, up to 1. Factorial comes from factor, indeed it is a big or long sequence of factors. If you denote the factorial by a bang, you can write the above formula in a more compact
way: n*(n-1)*..*(n-k+1)/k! If not still satisfied, you can put n! at the
numerator, but then to compensate you have to divide by (n-k)!, so you
have n!/((n-k)!k!) or n!/(k!(n-k)!) and this is the most compact form.

No comments: