The binomial coefficients

In the last post, we’ve finished talking about combinations and I mentioned there that the binomial coefficient are really important, so in this post I am going to focus on them and show some great properties of them.

This post is also going to be the first one that I use combinatorical proofs, they will make proofs much easier and intuitive!

Ok, let’s dive in!

The symmetry of the binomial coefficients

Here is a cool property:

{n\choose k}={n\choose n-k}

There is actually ‘nothing’ to prove here:

{n\choose k}=\frac{n!}{k!(n-k!)}=\frac{n!}{(n-k!)k!}={n\choose n-k}

The simplicty of of this statement is just ridiculous since from a first sight, you may not have intuition to why it’s true at all.

I want to give a combintarical proof that will make things a lot more intuitive:

Every time we pick a susbet with $k$ elements, we actually pick another set – the one who is made up of the elements you didn’t pick, which is of size $n-k$ . Thus, picking $k$ elements is equivalent to picking $n-k$ elements, hence the equality holds.

For example, if $n=4$ and you pick sets of $1$ element, you also pick a set of $3$ elements!

$\{1\}\leftrightarrow \{2,3,4\}$
$\{2\}\leftrightarrow \{1,3,4\}$
$\{3\}\leftrightarrow \{1,2,4\}$
$\{4\}\leftrightarrow \{1,2,3\}$

The Binomial theorem

One of the most famous formulas students learn in high school is:

(a+b)^2=a^2+2ab+b^2

The proof for it is nothing but a thecnical computation of one row:

(a+b)^2=(a+b)(a+b)=a^2+ab+ba+b^2=a^2+2ab+b^2

Ok, so we are familiar with it, some schools may even teach the formula for $(a+b)^3$ . don’t get me wrong though, even if your school never taught this, it’s not like a whole world is hidden from you. You can just simply this term yourself to get:

(a+b)^3=a^3+3a^2b+3ab^2+b^3

If your high school is “super advanced” he may taught you even how to simply the term $(a+b)^4$ , which is just so hard and only a few can learn it! Well… at least that what high school students would think about this formula. I think that you can do the exact same thing like you did before and simplfy the term. You don’t have to be ‘one of a kind’ to do so.

If you had no mistakes in your calculations, you should get:

(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^2+b^4

And I am a math major – I don’t care about those specific cases. I want to find a general formula for $(a+b)^n$ for any $n\in\mathbb{N}$ . So that’s what I am going to do.

Finding the formula

To get some intuition, I’ll look at the previous formulas and try to find some sort of pattern in them.

The first thing you probably see is that in all the formulas we have a sum of elements of the form:

a^{n-k}b^k

For example, in $n=4$ the elements of the sum are:

a^4\ \ \ \ (a^{4-0}b^0) \\ a^3b\ \ \ \ (a^{4-1}b^1) \\ a^2b^2\ \ \ \ (a^{4-2}b^{2}) \\ ab^3\ \ \ \ (a^{4-3}b^3) \\ b^4\ \ \ \ (a^{4-4}b^4)

Ok, that’s nice so now we know what to expect:

(a+b)^n=x_n\cdot a^n+x_{n-1}\cdot a^{n-1}b+\cdots+x_1\cdot ab^{n-1}+x_0\cdot b^n

Which we can wright in a more “compact” way using sigma:

(a+b)^n=\sum_{k=0}^ n x_{n-k}\cdot a^{n-k}b^k

The only thing left to figure out are the coefficients – the $x_i$ -s.

So now I am going to use a combinatorical argument to do so, and on the way, prove what we just concluded here.

Let’s write $(a+b)^n$ as a product

(a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)}_{n\text{ times}}

Now, think of each factor in the product as a box. Each box has to elements in it – $a$ and $b$ . Therefore, when simplifying the term, we will get sum of product $a$ -s and $b$ -s. Some examples for the product are:

a\cdot b\cdot b\cdot b\cdot a\cdot a \cdot a\cdot b\cdot b\dots \\ b\cdot a\cdot b\cdot a\cdot a\cdot a\cdot b\cdot b\cdot b\dots

And we have many ways of doing so. How many to be exact? So if care about the order of the selection, and we allow repititions we’ll have 2 options to select from in the first box. 2 options to select from in the second box… In total we would have $2^n$ options of doing so (convince yourself!).

However, we don’t realy care about the order of the selection – $a\cdot b$ is the same as $b\cdot a$ .

Moreover, I can write those products in a simpler way – as powers of $a$ and $b$ , where the sum of thier powers has to be $n$ (since we pick $n$ elements)

Now the question is, in how many ways I can ‘create’ the element $a^{n-k}b^k$ . An equivalent question would be to ask: “In how many ways, you can choose $b$ from $k$ different boxes?”

Well, we know the answer for it – there are exactly “ $n$ choose $k$ ” options. That is: ${n\choose k}$ .

And that’s pretty much tells us the whole story. The coefficient of $a^{n-k}b^k$ is ${n\choose k}$ – since we have $n\choose k$ different options of creating the element $a^{n-k}b^k$ .

This yields the formula:

(a+b)^n=\sum_{k=0}^ n {n\choose k}a^{n-k}b^k

This formula is called the binomial theorem it’s called a theorem since it so useful, you will run into it everywhere! And we can prove with it some really non-trivial result! Let’s see some:

Using the binomial theorem

Number of subsets

If we plug in $a=1,b=1$ we will get:

(1+1)^n=\sum_{k=0}^n{n\choose k}1^{n-k}1^k\\ \Downarrow \\ 2^n= \sum_{k=0}^n{n\choose k}

And that’s a pretty cool identity!

I want to present another proof fot it, a combinatorical one – I am going to show that both sided of the identity represents the same thing.

For the left side, $2^n$ , I know exactly what it is. It is the number of subsets of the set $\{1,2,\dots,n\}$ . Why? since we can describe each subset as:

1 is in it / not
2 is in it / not
3 is in it / not
4 is in it / not

And so on… For every number we have 2 option – whether you are in or you are out. We have $n$ elements in the set. Thus, there are $2^n$ different subsets.

On the other hand, note that $n\choose k$ is the number of subsets of size $k$ of the set $\{1,2,\dots,n\}$ . And we are summing up over all the possible $k$ s, which yields the number of subset of the set $\{1,2,\dots,n\}$ .

We found out that both sides count the same thing, hence they are equal!

Plus and minus

Similarly, we can now plug in $a=1, b=-1$ , and we’ll get:

(1+(-1))^n=\sum_{k=0}^ n {n\choose k}1^{n-k}(-1)^k \\ \Downarrow \\ 0=\sum_{k=0}^ n {n\choose k}(-1)^k ={n\choose 0}-{n\choose 1}+{n\choose 2}-\dots+(-1)^n{n\choose n}

And that’s another cool identity!

Pascal’s triangle

It turns out that we describe the binomial coefficients in a recursion:

{n\choose k}={n-1\choose k-1}+{n-1\choose k}

Let’s prove it in a combinatorical way:

The left side of the equation is the number of subsets with $k$ elements of the set $\{1,2,\dots,n\}$ .

The right side is a bit more complicated:

Suppose we want to count the subsets with $k$ elements where $n$ is in all of them. How many are there?

So after we picked the number $n$ to be an elements of the subsets, we have to pick $k-1$ more out of $n-1$ elements. That is ${n-1\choose k-1}$ .

Now, how many subsets with $k$ are there such that $n$ is not in any of them.

We can only pick $n-1$ elements since $n$ is not allowed. And we need to pick $k$ of them. That is ${n\choose k}$ subsets.

Adding both of the numbers and we have the right side of the equation. However, their sum represents exactly the number of subsets with $k$ elements!

Therefore, both sides represent the same thing, hence the equality.

Great, so after we proved that, we can present a triple of binomial coefficient with some sort of a triangle:

By defining ${n\choose0}={n\choose n}=1$ , we can get a ‘triangle’ that represent the recursion:

This triangle is called the pascal triangle. We can write the binomial coefficients as numbers and get the trinagle:

And there is a really cool animation that demonstrates it really well:

Are those numbers look familiar? It’s pretty obvious when you notice it, but the numbers in the $n$ -th row represents exactly the coefficient of $(a+b)^n$ !

You can do a lot of things with this trinalge, it shows up in many unexpected places. If you wish, there’s a lot stuff you can read about them in the wikipedia, but I’ll stop here since I want to present more things other than the triangle.

The captain identity

Suppose that you are basketball team manager. For some reason, you have no players at your team and the season starts in two weeks!

Well, you’ve got to do something about it, right? In order to participate in the league’s games you need exactly $k$ players.

Your scouters did a good job and not only they’ve found $k$ players, they’ve found even more – $n$ players.

Great, you now have rich people’s problems – first you had no players, and now you need to choose $k$ of them. However, you also need to choose a captain to your team – since every team has a captain.

Now my question is, in how many ways you can pick $k$ players where one of them will be the captain?

There are two ways to approach it:

Choose $k$ players out of $n$ and then choose a captin from those players.
Choose a caption and then choose the other $k-1$ players.

In the first way, you first choose ${n\choose k}$ players, and then you have $k$ different options. Thus, the number of possible selections is:

{n\choose k}k

In the second way, first you have $n$ options for a captain, and then you have to choose $k-1$ out of $n-1$ player, you have ${n-1\choose k-1}$ options to do so. Multiply it by the number of choices of a captain to get total of:

{n-1\choose k-1}n

different choices.

Since both cases represent the same amount of choices, they are equal, and we’ve just proved the captain’s identity:

{n\choose k}k={n-1\choose k-1}n

One statement – Three proofs

I now want to present a statement which I am going to prove using the captain’s identity. However, I’ll prove the same statement in two more ways – where one of them is really unexpected!

The statement is:

\sum_{k=0}^n{n\choose k}k=n\cdot2^{n-1}

Proof 1 – The captain’s identity

Note that the sum starts at 0, and when substituting $k$ for 0, we will get 0 in the term inside the sum. Thus:

\sum_{k=0}^n{n\choose k}k=\sum_{k=1}^n{n\choose k}k

We now use the identity to get:

\sum_{k=1}^n{n\choose k}k=\sum_{k=1}^n{n-1\choose k-1}n =n\sum_{k=1}^n{n-1\choose k-1}=n\sum_{k=0}^{n-1}{n-1\choose k}=n\cdot2^{n-1}

Where the last transition follows form this identity.

Proof 2 – Combinatorical proof

The left side represents the number of ways to pick a captain from a team with unknown number of players (it can be anything between 0 and $n$ ).

The right side is the number of choices when you first choose a player, and then choose a subset of the rest of the players from any size (Recall that $2^{n-1}$ is the number subsets of a set with $n-1$ elements). That’s exaclty the number of choices of teams with a capting an unknown size.

Thus, both of them represent the same number, hence the equality holds.

Proof 3 – The binomial theorem and calculus

Yes, you read it right, I am going to use calculus to prove it, though it’s going to be really basic calculus.

Let’s define the function:

f(x)=(1+x)^n

By the binomail theorem we know that:

(x+1)^n=\sum_{k=0}^n{n\choose k}x^{k}

Thus:

\frac{d}{dx}[(x+1)^n]=f^\prime (x)=\frac{d}{dx}[\sum_{k=0}^n{n\choose k}x^{k}] \\ \Downarrow \\ n(x+1)^{n-1}=\sum_{k=0}^n{n\choose k}k\cdot x^{k}

Subsitute $x = 1$ to get:

n(1+1)^{n-1}=\sum_{k=0}^n{n\choose k}k\cdot 1^{k} \\ \Downarrow \\ n2^{n-1}=\sum_{k=0}^n{n\choose k}k

As we wanted!

Summary

So we’ve seen many cool properties of the binomail coefficients. Moreover, we used the method of a combinatorical proof for the first time, and they are really fun in my opinion. And of course, we’ve proved the binomail theorem, which is one of the most useful theorems that we will use a lot, and not just in combinatorics!

The symmetry of the binomial coefficients