# Combinations

In the last post I’ve talked about permutations. In this post I am going to keep doing what I’ve started there – by introducing the the term of combinations:

## What are Combinations?

A Combination of $k$ out of $n$ objects is a selection, where order doesn’t matter. Same as permutation, there are two types of combinations:

• combination with mutiple selections.
• combination without multiple selections.

#### Multiple selections – not allowed

We already know the answer for this question when order matters, it is $(n)_k$. However, here the order doesn’t matter – so some choices may be considered as the same.

Let’s demonstrate it, Suppose that we have 4 balls (1,2,3,4) and we want to pick 3 of them. When order matters, the options are:

• $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$
• $(1,2,4),(1,4,2),(2,1,4),(2,4,1),(4,1,2),(4,2,1)$
• $(1,4,3),(1,3,4),(4,1,3),(4,3,1),(3,1,4),(3,4,1)$
• $(4,2,3),(4,3,2),(2,4,3),(2,3,4),(3,4,2),(3,2,4)$

That makes since we have found that the number of options is $(4)_3=\frac{4!}{(4-3)!}=4!=24$.

However, when order doesn’t matter, every row in the above is consider only as one way of selecting 3 out of 4. For example:

(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)

are all considered as the same selection – they are equivalent.

Therefore, the number of selections possible is:

\frac{\text{The number of selections when order matters }}{\text{The number of equivalent choices}}

We already know what ‘The number of selections when order matters’ is – it is exactly $(n)_k$.

The only thing left to find out is how many selections are equivalent to each other. Let’s represent a selection as a sequence:

(x_1,x_2,\dots,x_k)

We have $k$ objects in a selection: $x_1,\dots,x_k$. And we have $k$ ‘spots’ in the parentheses:

([\text{spot }1],[\text{spot }2],\dots,[\text{spot }k])

The question is – In how many ways can we arrange the objects in the spots. However, we know how many ways are there – since this exactly the number of permutations of $k$ out of $k$ objects!

i.e. it is the the number of choices to pick $k$ objects (competings) out of $k$ objects. Which is:

(k)_k=\frac{k!}{(k-k)!}=\frac{k!}{0!}=k!

Thus:

\frac{\text{The number of selections when order matters }}{\text{The number of equivalent choices}}=\frac{(n)_k}{k!}=\frac{\frac{n!}{(n-k)!}}{k!}=\frac{n!}{k!(n-k)!}

And that is what we were looking for!

#### The Binomial Coefficient

We have found out that the number of combinations of $k$ out of $n$ objects is exactly $\frac{n!}{k!(n-k)!}$. This number is really important. In fact, it is so important that it has a name: “The Binomial Coefficient” (We will understand where this name came from in the future).

It it also denoted as:

{{n}\choose{k}}

And we read it / call it : “n choose k”.

Remember those names, since we will use a lot.

##### Quick example

Suppose that you are a teacher, and you have $20$ students in your class. You need to pick 15 different students. In how many ways you can do so? Well the answer is “20 choose 15”:

{20\choose 15}=\frac{20!}{15!(20-15)!}=\frac{20!}{15!\cdot5!}=15,504

The term “ $n$ choose $k$” is so common that even google is familiar with it:

#### Multiple selections – not allowed

Ok, we have reached the last option – which is the most complicated one. Don’t worry though – we’ll get over it!

###### Step 1 – matching a selection with a sequence

The best thing to do is just to look at concrete example first. Suppose that I am picking 7 objects out of 5. I’ll denote the set of the objects as:

\{1,2,3,4,5\}

One possible way to do so is to pick the objects:

1,2,3,1,1,3,4

Recall that it doesn’t matter what we pick first. Beacuse of this fact, I want represent this choice in non-decreasing order:

(1,1,1,2,3,3,4)

This sequence represents all the ways of choosing the exact number.

In general, if we picked the objects $x_1,x_2,\dots,x_k$ such that:

x_1\leq x_2\leq \dots\leq x_k

Then the non-decreasing sequence that represents that coice is:

(x_1,x_2,\dots,x_k)
###### Step 2 – Adding ‘bars’

Let’s look at our example again. The sequnce we chose was:

(1,1,1,2,3,3,4)

I am now going represent it a bit different:

(1\ 1\  1 \ |\ 2\ |\ 3\ 3\ |\ 4\ |)

I’ve added ‘bars’ to the sequence between any two numbers that are different.

(1\ 1\  1 \ |\ 2\ |\ 3\ 3\ |\ 4\ |\ )

In general, if:

a_1=a_2=\cdots=a_{k_1} < b_1=b_2=\cdots=b_{k_2} < m_1=m_2=\cdots=m_{k_l}

Then we add bars like that:

( a_1\ a_2\ ...\ a_{k_1} \ |\ b_1\ b_2\ ...\ b_{k_2}|\ \dots\ |\ m_1\ m_2\ \dots \ m_{k_l})

Note that if a sequnece doesn’t contain some number, we still add bars to represent where it ‘should’ be in case it wasn’t missing. For example, the sequnce:

(1,1,1,2,2,2,4)

Will be represented as:

(\ 1\ 1\ 1\ |\ 2\ 2\ 2\ |\ |\ 4\ |)
###### Step 3 – Replacing the numbers

Now, I am going to switch the numbers with * :

(*\ *\ * \ |\ *\ |\ *\ *\ |\ *\ |\  )

Notice that we haven’t lost any information – the bars show us what is the value of each *. In other words, this action is invertible (try it – write * and | in any order you want, then try to find the corresponding sequence).

In this example we have

• 7 ‘stars’ – *
• 4 (= 5-1) ‘bars’ – |

Recall that this was a selection of 7 objects from 5 objects – this gives us sort of an idea to what happens in the gerneral case.

In the general case where we pick $k$ objects out of $n$ there will be:

• $k$ ‘stars’ – ‘*’
• $n-1$ ‘bars’ – |
###### Step 4 – Conculding the answer

So every sequnce has $k$ stars and $n-1$ bars. We can treat them all as objects. Thus we have $k+n-1$ objects in any sequence.

Now for the trick:

From all of the $k+n-1$ spots available in the sequence. In $k$ from them we need to place a star. In how many ways we can do so?

This is exactly the question:

“How many ways are there to pick $k$ spots from $k+n-1$ spots”

And we know the answer for it! The answer is “ $k+n-1$ choose $k$” or:

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

And that’s it! That’s what we were looking for!

Notice one more thing: Our question is also equivalent to determine the number of ways we can place bars. Since there are $n-1$ bars, the number of options is:

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

And that’s also an answer. This answer yields a really cool identity:

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

We can plug in values of $k$ for some interesting results: for $k=0$ we have:

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

and for $k=1$:

{{n}\choose{1}}={{n}\choose{n-1}}
##### Quick example

How many positive integer solutions the equation:

x_1+x_2+x_3=8

has? For example, valid solutions are:

x_1=0,x_2=0,x_3=8
x_1=4,x_2=0,x_3=4
x_1=3,x_2=2,x_4=3

The trick for the solution match the question to sonething we are already familiar with:

Let’s look at the first solution. Notice that I can read the solution like:

“We pick 0 $x_1$, 0 $x_2$ and 8 $x_3$

You thing you got it? If not, let’s see what about the third solution

“We pick 3 $x_1$, 2 $x_2$ and 3 $x_3$

Notice how I am treating the variables as objects, and in total I am picking 8 objects, and we can select objects more than once.

Therefore the number of the solutions to the equation is exactly the number of ways to pick $k=8$ objects out of $n=8$ when Repetitions are allowed and order doesn’t matter. Therefore, the answer is:

{{n+k-1}\choose{k}}={{8+3-1}\choose{3}}={10\choose3}=\frac{10!}{3!7!}=120

## Completing the table

We can now summarize all of our results in a table. Suppose we pick $k$ out of $n$ objects. Then the number of selections according to the specific rules is:

## Summary

After all the cases are covered, we now have quite great tools to count selection of objects.

We’ve also met the binomial coefficient that plays a big role all around math.

However, there are still more counting problems we are not able to solve yet. But that’s on the next post…