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 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 . 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 chess board.

Easy right? now try covering a 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 board has squares, while a board has squares. In general, board has 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 board** if and only if** is even. Let’s try to prove it.

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

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

Notice that represents the number of rows, or the ‘length’ of each column. That means that each column has a size of . 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 is even, is an Integer, thus each column will be covered by 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 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 board. Let’s begin with , will denote the number of covers.

It is not hard to see that there is only **1** cover. We get that . Let’s proceed to

You can try it yourself and get that there are **2** covers, we can place two dominoes horizontaly (=), and two dominoes vertically (||). Thus, . 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 . Right now it seems like that in general . It is though? let’s see what’s happening when :

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 is, and you will get that . 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

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

In simpler words, the 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 , and our sequence starts at . We will try to prove that our sequence is the fibonacci sequence by **induction**.

#### The proof

The cases (and even ) were already covered. We now assume that the statement holds for every and we will prove it holds for as well.

I am going to count the number of covers using smaller board within the original board. Consider a 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 . And we know that there are different covers for this board. thus, we add to our count the number .

Another possiblilty is:

From similar, the number of covers here is exactly . Then we add to our count . We have two more options:

Each one of those cases adds to the count 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: and . 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 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** 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 .

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.