Binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. Binomial coefficients have been known for centuries, but they're best known from Blaise Pascal's work circa 1640. Below is a construction of the first 11 rows of Pascal's triangle.
In mathematics, binomial coefficients are represented as , where is the row, and is the number in that row, counting from the left, acting as an index. That is under the pretense that the first row is usually considered to be the row, which is what we will be assuming as well. For example, the number in the row is represented as . Binomial coefficients, which are in the form , are equal to the number of ways there are to choose objects from a set of objects.
Binomial coefficients are the ones that appear as the coefficient of powers of in the expansion of
where The terms from to are called as the binomial cofficients. Hereafter the term will be written as
Calculate the value of .
We can use the formula to calculate the value of :
Calculate the value of .
We can use the formula to calculate the value of :
In how many ways can you select 2 balls from a box containing 9 balls?
The number of ways to choose 2 elements out of a set of 9 is
In how many ways could you choose a three-topping pizza based on the following menu?
The number of ways to choose 3 elements out of a set of 10 is
Three distinct numbers, are chosen at random such that . What is the probability that their product is divisible by 9?
What this question is really asking is "how many and can be chosen so that, combined, has a power of which is " It seems our best bet is to factorize each number from to
Our instincts tell us that it may be easier to count the numbers that are not divisible by 9, and then subtract that value from the total numbers we can make. Following this logic, we build two cases:
- Case 1: The highest power of that divides is .
There are numbers in the interval that are not divisible by , and we want to choose of them. Thus, for this case, all we need to calculate is .
- Case 2: The highest power of that divides is .
There are numbers in the given interval which have a highest power of with magnitude . We can choose only one of these for our variables. The other two variables must come from the set we considered in case . So, we have to calculate . Thus, we have a total of numbers which are divisible by .
Now, we recognize that there are total combinations of choices of numbers from to . Thus numbers formed in this manner divide . Hence, the probability is .
How many 3-digit numbers can be formed by using 1, 2, 3, 4, 5 without repetition of digits?
Here making a 3-digit number is equivalent to filling 3 places with 5 numbers.
So, the number of ways of filling all the three places is
But note that the order of these 3 distinct digits matter! So we need to multiply it back by .
Hence, the total possible 3-digit numbers from the above 5 numbers is .
As the name implies, the binomial theorem can be used to expand binomials. You may do so with the equation below.
When given a binomial, , you may expand the binomial using the following equation:
This is a simplified definition of binomial expansion using binomial coefficients.
This equation may seem overwhelming at first glance. However, an easy way to think about it is that you apply each coefficient to its appropriate term, and the power of the first binomial term counts down from to 0, while the power of the second binomial term counts up from 0 to
Using the equation given above, we know that and . Therefore we can expand the binomial to
Find the coefficient of in the expansion of .
Recall that the binomial theorem is
which in summation form is
In order to get the coefficient of , we need to have Sinces , .
Thus, the answer is
Extracted from mathematician Blaise Pascal's famous triangle, binomial coefficients have several elegant properties. Sure, they're useful, often necessary, in combinatorial analysis, but they're much more than that. Some properties make use of symmetry, some deal with expansion, but they all can be proved rather intuitively. We start by looking at binomial coefficients in their most raw form: in Pascal's triangle.
From the above diagram, we can see that the basic rule of construction is
Or, in other terms, the sum of two adjacent binomial coefficients is equal to the one "below" it, assuming Pascal's triangle is produced in the equilateral-triangle-like shape shown above. Another important identity is
This is the statement that each row of Pascal's triangle is symmetric in either one of two ways. It is either palindromic and centrally oriented (for even ), or palindromic and "mirrored," where all the numbers on one side of the triangle are replicated on the other side (for odd ).
The sum of binomial coefficients across a fixed row is equal to a power of two. Indeed,
which can easily be shown by
Along similar lines, I'll demonstrate a more general fascinating property concerning a weighted sum of binomial coefficients with respect to their indices:
First, we take note of what this sum looks like:
The first term is zero, so let's rewrite our sum as
Falling back on the formula to calculate a binomial coefficient, we obtain
which is quite advantageous for us, considering we have a fixed . We can finally say that
Then it follows from our earlier definition for the sum of binomial coefficients that
Now comes something interesting. The alternating sum of binomial coefficients across a fixed row equals . More formally,
It follows that
Let equal the sum of all the even-index terms in row , and let equal the sum of all odd-index terms in row . Our previous equation now can be shown as
Since the sum of all the even-index terms in row and the sum of all the odd-index terms in row are equal, they contribute the same amount to the total sum of the row, . Thus, if we omit either the even-index or the odd-index terms, we will have precisely half of our original total. Thus, we can say
One may also notice a familiar sequence hidden in Pascal's triangle. represents the triangular number . If you're unfamiliar with this sequence, here is a link to get you started! This proof makes use of the facts that
and making the assumption that for all ,
which holds under induction. We can verify this visually by looking at Pascal''s triangle and using our guideline for construction:
Now, if you know your stuff about triangular numbers, you can say that
It is left to the reader to prove this for themselves, but if you get stuck, here's a link to the proof.
One of the more visually striking properties is the Sierpiński sieve, which is obtained by taking mod 2 of every binomial coefficient. This process separates each binomial coefficient by its parity. If every odd number is replaced with a black triangle, a Sierpinski triangle begins to form. Try it out for yourself! This also plays into the Lucas correspondence theorem, which is left for the reader to discover for further learning.
Suppose we have a sequence of length , and we want the number of ways to choose elements. Obviously, there are choices for the first element. There are ways to choose the second element, ways to choose the third element, etc. This continues down to choosing the element, for which there are choices. Thus the number of all possible permutations of these "choosings" is
Now, for all these selections, there are only some unique ones. In other words, some selections are permutations. It's easy to see that there are permutations of each primitive selections. Thus, to get the number of primitive sequences, we use
Intuition: The above sum is equal to the number of ways we can choose object from objects plus objects all the way up to choosing objects. Intuitively, this is all possible "choosings" for objects. Now, if we are to calculate the total possible "choosings" for objects, since each object can be either chosen or not chosen, this is equal to