Now, we're ready to give a definition.
So if we have a set, S, then it's k-combination is a subset of size k, okay?
So, and the number of different such subsets of size k
is denoted by n choose k.
So where n is the size of the set S.
So more precisely or more formally, n choose k is defined with the number
of different subsets of size k, of an n element set.
And once again, it is pronounced as n choose k, and
it is written like this, okay?
So, this is a very important combinatorial quantity.
So in particular, you can go to Google and compute any such number.
For example, if you compute 5 choose 3 in Google,
it will give you a result, okay?
Once again, it is 10.
So there are ten ways of choosing three of your friends out
of five of your friends, okay?
Now, before giving the formula, let's look once again
at the difference between the number of 3-combinations and 3-permutations.
So let's list all possible 3-permutations.
So recall that in a 3-permutation, we just would like to put one of your five
friends to the first place, then one of the remaining four friends to the second
place, and then one of the remaining three friends to the third place.
So this gives us 5 x 4 x 3 which is 60, and all 60 permutations,
3-permutations are shown here on the slide.
And they are arranged in a nice way such that as you see in the same column,
we have exactly the same three elements permuted, right?
And we know that for elements abc,
there are exactly 3 factorial possible ways of permute them, right?
So in which means that the number of 3-permutations
is 3 factorial larger than the number of 3-combinations.
More precisely, what we see here is that in this table, the height of this table is
3 factorial while the width of this table is 5 choose 3.
At the same time,
the total size of the elements in this table is the number of 3-permutations.
And we know how to compute it.
The number of 3-permutations is 5 x 4 x 3
which is nothing else as 5 factorial divided by
2 factorial which is just 5-3 factorial.
So this gives us the following formulas.
The number of elements is equal to the height of this
table times the width of this table, okay?
And this will lead us, this substitution will lead us to the general formula for
computing n choose k.
So the formula is as follows.
n choose k is equal to n factorial divided by k factorial,
and divided by n minus k factorial, okay?
So this is the formula and now let's try to prove it.
So we have actually everything needed to prove it already, okay?
So first, let me remind you that n choose k is the number of
subsets of size k out of n elements, okay?
Now, first, let's count the number of k-permutations, okay?
So, for k-permutations, there are exactly n choices for the first element.
Then there are n-1 choices for the second element, n-2 choices for
the third element and so on.
(n- k +1) choices for the k-th element.
And this computes the number of k-permutations.
And we know already that it is equal to n factorial divided by (n-k) factorial.
Which is just a convenient way of writing the expression n times
(n-1) times (n-2) times (n- k + 1), okay?
And this says, as we've discussed already,
this computes the number of k-permutations but not the number of k-subsets.
And the number of k-permutations is exactly k
factorial times larger than the number of k-subsets, right?
Why is that?
Well, because just when we count the number of k-permutations,
every subset is counted exactly k factorial times.
Because if you have a subset of size k,
there are k factorial ways of permuting its elements, right?
Which finally gives us the estimate n factorial divided n minus k factorial.
Let me remind you that this part, n factorial divided by n minus k factorial,
is exactly the number k-permutations.
And we need to divide it by k factorial to finally
get the number of different k subsets, okay?
So once again, let me show you the results and estimate.
So n choose k is equal to n factorial divided by
k factorial divided by n minus k factorial.