In this lesson, we'll talk about Binomial Coefficients.
To introduce some concepts, consider the following problem:
How many ways can we select a subset of items from a collection of items?
Since we're talking about sets, the order of the items doesn't matter. So the set is equal to the set and for example.
We have possibilities to the first item. To the second item, we have possibilities, since we have already choosed one (the first). To the second, there's possibilities. In general, we have possibilities for the -th item. Then our answer would be . But this answer is considering the order of the elements. Each set is being counted times since all permutations of the set are being counted. So our real answer is .
To represent the answer more elegantly, we will manipulate it a bit. We will multiply the numerator and denominator of this fraction by . So, we'll get the following formula: . By doing this, we apparently only complicate our answer. However, if we look more carefully at the numerator of this fraction, we can see that this number is . It means that our answer is equal to . This representation of the answer is much friendlier than the answer we originally had.
Since this is a commom subproblem of many mathematical problems, we represent this number with a symbol: . That is, . These symbols are known as Binomial Coefficients. Generally, we refer to the number as choose . We only need to be careful when . In this case, we consider that is equal to .
The binomial coefficients have a lot of applications in mathematics and a lot of properties. In this lesson, we'll learn some properties and how to calculate of efficient ways in programming.
Let's first see some properties of them:
