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 out of 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.

Let’s start with the second type:

Multiple selections – not allowed

We already know the answer for this question when order matters, it is . 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:

That makes since we have found that the number of options is .

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 .

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 objects in a selection: . And we have ‘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 out of objects!

i.e. it is the the number of choices to pick objects (competings) out of 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 out of objects is exactly . 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 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 “ choose ” 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 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 objects out of there will be:

• ‘stars’ – ‘*’
• ‘bars’ – |

Step 4 – Conculding the answer

So every sequnce has stars and bars. We can treat them all as objects. Thus we have objects in any sequence.

Now for the trick:

From all of the spots available in the sequence. In 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 spots from spots”

And we know the answer for it! The answer is “ choose ” 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 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 for some interesting results: for we have:

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

and for :

{{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 , 0 and 8 “

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

“We pick 3 , 2 and 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 objects out of 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 out of objects. Then the number of selections according to the specific rules is:

	Repetitions allowed	Repetitions are not allowed
Order matters (Permutations)
Order doesn’t matter (Combinations)

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…