Combinatorics - Introduction

Hey! Welcome to the first combinatorics posts. What is combinatorics? It is actually a very wide subject, that appears everywhere in math. Basic Combinatorics can answer questions such as:

If 1,000 people choose between two thing, in a random way, what is the chance that 500 chose the first thing, and the other 500 chose the second?
Is there a fibonaci number which ends with 1,000 zeroes?
What are the odds that a matrix $A\in M_n(\mathbb{Z}_2)$ is invertible?
Given 30 people, how many different ways to choose 5 people from them are there?

There are 4 main subject that we study in combinatorics: Existence, counting, sorting and optimization.

In this post I am going to present an example, which demonstrates the first two subject: Existence and counting.

Chess & Domino

Our goal for the rest of the post is to cover sorts of chess boards with dominoes. Each domino fits into two cells of a chess board, in other words, a domino piece’s dimentions are $2\times 1$ . The first question we are going to ask ourselves is whether or not is it even possible to cover the borad. For example, try covering a $4\times 4$ chess board.

Easy right? now try covering a $3\times 3$ board. You will quickly realize that this is an impossible task.

Can you think of a reason why? In order to determine when we can cover a board by dominoes or not, I want to look at the number of sqaures in it.

For example, a $4\times 4$ board has $16$ squares, while a $3\times 3$ board has $9$ squares. In general, $m\times n$ board has $m\cdot n$ squares.

A single domino fills up 2 sqaures from the board, thus every time we add a domino we are covering some even number of squares from the board. This leads us to think that we can cover a $m\times n$ board if and only if $m\times n$ is even. Let’s try to prove it.

Suppose that we can cover the board with $k$ dominoes. Beacuse each domino covers 2 squares, we have covered $2k$ squares. Recall that this is a cover, thus the number of sqaures covered equals the total number of squares, thus $m\cdot n = 2k$ and we got that $m\cdot n$ is even.

On the other hand, Suppose that $m\cdot n$ is even, then one of them must be even, or else their product will be odd, WLOG, $m$ is even.

Notice that $m$ represents the number of rows, or the ‘length’ of each column. That means that each column has a size of $m\times 1$ . We can now cover each column separately, placing a domino on the 2 upper squares, and then just keep placing more dominos toward the bottom.

Since $m$ is even, $\frac{m}{2}$ is an Integer, thus each column will be covered by $\frac{m}{2}$ dominoes.

Ok, that solved our problem, let’s make it a little bit more challenging, What happens if we remove the upper left corner square and the lower right corner square? An $8\times 8$ board will look like this:

How can we approach such a question? The key here is to look at the color of the squares. As you see, each sqaure is colored by black or white, where next to a black square, there are white squares and next to white squares, there are black squares. Notice that every domino fills up exactly one black square and one white square. That means if there is a cover, the number of black squares must be the same as the number of white squares. In this specific board we have 32 black squares, however, there are only 30 white squares, thus, a covering for this board is just not possible!

Counting covers

So we have only discussed the existence of covering, now I want to discuss the number of covering. We are going to find out how many possible covers are there for a $2 \times n$ board. Let’s begin with $1$ , $a_n$ will denote the number of covers.

It is not hard to see that there is only 1 cover. We get that $a_n=1$ . Let’s proceed to $2\times 2$

You can try it yourself and get that there are 2 covers, we can place two dominoes horizontaly (=), and two dominoes vertically (||). Thus, $a_2 = 2$ . What about 3?

Again, you can try it yourself and find out that there are 3 options:

(Every line here represents a domino). then we have $a_3 = 3$ . Right now it seems like that in general $a_n=n$ . It is though? let’s see what’s happening when $n=4$ :

Try it! Here something wired is happennig, it turns out that there are 5 covers!

||||
||=
=||
|=|
==

So our assumption from before is wrong. Let’s look at our sequnece so far:

a_1=1,a_2=2,a_3=3,a_4=5

You can try to find out what $a_5$ is, and you will get that $a_5 = 8$ . our sequnce now is:

1,2,3,5,8,...

I am sure some people may be already thinking of a famous sequnece right now, I am talking about the fibonacci sequence, which is defined by recursion:

a_0=a_1=1

and for $n\geq 2$

a_n=a_{n-1}+a_{n-2}

In simpler words, the $n^{th}$ element is the sum of the previous two elements. Fibonacci sequence first elements are:

1,1,2,3,5,8,13,21,...

Our sequence is quite similiar to it, the only difference is that there is an ‘extra’ 1 at the beginning of the fibonacci sequence. However, that is not really a problem since fibonnaci sequence starts at $n=0$ , and our sequence starts at $n=1$ . We will try to prove that our sequence is the fibonacci sequence by induction.

The proof

The cases $n=1,2,3$ (and even $4,5$ ) were already covered. We now assume that the statement holds for every $k<n$ and we will prove it holds for $n$ as well.

I am going to count the number of covers using smaller board within the original board. Consider a $2\times n$ board:

(I know it 2 by 8, but I won’t think of it like that). We will start by checking In how many ways we can cover the sides.

That’s one way to do so, As you can see, the area marked in red is exactly the borad of size $2\times (n-2)$ . And we know that there are $a_{n-2}$ different covers for this board. thus, we add to our count the number $a_{n-2}$ .

Another possiblilty is:

From similar, the number of covers here is exactly $a_{n-4}$ . Then we add to our count $a_{n-4}$ . We have two more options:

Each one of those cases adds to the count $a_{n-3}$ new covers. What we have got now is that:

a_n=a_{n-2}+a_{n-4}+2a_{n-3}

We can play with it a litlle bit to get:

a_{n-2}+a_{n-4}+2a_{n-3}=a_{n-2}+a_{n-4}+a_{n-3}+a_{n-3}

=a_{n-2}+a_{n-3}\ \ +\ \ a_{n-3}+a_{n-4}

Recall that by induction: $a_{n-2} + a_{n-3} = a_{n-1}$ and $a_{n-3} + a_{n-4} = a_{n-2}$ . Which gives us:

a_n=a_{n-1} + a_{n-2}

As we wanted!

Fibonacci in code

There is actually one small thing I would like to show that is related to the fibonacci sequnece and that is how write in code a function that calculates the $n^{th}$ element of the sequnece.

int fib(int n) {
   if (n == 0 || n == 1) return 1;
   else return fib(n-1) + fib(n-2);
}

This is such a simple code (that actually has the exact same syntax in a lot of programming languages), it is also one of the very first examples of recursion.

The function gets an integer $n$ as an input. If it is 0 or 1, the output will be 1. else the outpout will be the sum of the previous two. What happens is that the function is calling itself. Le’ts see how it calculates $a_3$ .

We are starting with n=3. This is not 0 or one, so we now need to calculate the sum fib(2) + fib(1). when you plug in 1 to the function, you get 1, so fib(1) = 1. Now for fib(2). again n is not 0 or 1, thus we need to calculate fib(0) + fib(1), however, we know that fib(0)=1 and fib(1)=1 thus fib(2) = 2. After that we get that fib(2) + fib(1) = 2 + 1 = 3 and that is the output of the function.

Summary

I think that this is enough for a first post, throughout future posts we will develop new tools and will be able to answer questions like the one I have presented above.

Combinatorics – Introduction

Chess & Domino

Counting covers

The proof

Fibonacci in code

Summary

Like this:

Leave a Reply Cancel reply

Chess & Domino

Counting covers

The proof

Fibonacci in code

Summary

Share

Like this:

Leave a Reply Cancel reply