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.

Let’s start with the second type:

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:


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:


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:



\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:


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:

Try 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:


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


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


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:

Step 2 – Adding ‘bars’

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


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:


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:


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


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


and for k=1:

Quick example

How many positive integer solutions the equation:


has? For example, valid solutions are:


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:


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:

Repetitions allowedRepetitions are not allowed
Order matters (Permutations)n^k(n)_k=\frac{n!}{(n-k)!}
Order doesn’t matter
{k+n-1\choose k}={k+n-1\choose n-1}{n\choose k}=\frac{n!}{k!(n-k)!}


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…

Leave a Reply

%d bloggers like this: