Faces of Fibonacci

You know about the Fibonacci numbers and you know how Matrix Exponentiation allows you to find the nth Fibonacci number in just O(logn) time.

Matrix Exponentiation is a useful tool in solving not just the questions related to Fibonacci numbers but other recurrence equations too.

The equation:
f(n) = a*f(n-1) + b*f(n-2)
can be disguised and thrown at you in numerous ways.

I’m going to use a familiar problem to show you how.


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1
2. size 2 X 1
In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


To form rectangle of size 1 X 1 there is only one way. That is to use one rectangle of size 1 X 1.
To form rectangle of size 2 X 1 there are two ways: the first is to use a 2 X 1 rectangle directly and the second way is to put two 1 X 1 rectangles side by side.
To form rectangle of size 3 X 1 there are 3 ways. For 4 X 1, there are 5 ways..

Lets analyze this problem in a recursive manner:

Let f(n) be the number of ways to form an N X 1 rectangle.
An N X 1 rectangle can be formed either by adding a 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
Therefore, the number of ways to form N X 1 rectangle = (number of ways to form (N-1) X 1 rectangle) + (number of ways to form (N-2) X 1 rectangle)
f(n) = f(n-1) + f(n-2) ; with f(0)=1 and f(1)=1
Its the Fibonacci series!!

( f(0)=1 because there is 1 way to form a 0 X 1 rectangle: do not use any rectangle )

Let’s look at a variation.


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of two different types: red- and blue-colored
2. size 2 X 1

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


An N X 1 rectangle can be formed either by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
OR
by adding a blue 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a red 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
So, there are two ways to obtain N X 1 rectangle from an (N-1) X 1 rectangle, and only one way to get it from an (N-2) X 1 rectangle.
The equation becomes f(n) = 2*f(n-1) + 1*f(n-2) ; with f(0)=1 and f(1)=2

In general, if we have 1 X 1 rectangles of X different colors and 2 X 1 rectangles of Y different colors, we can make an N X 1 rectangle in f(n) ways, f(n) = X*f(n-1) + Y*f(n-2); with f(0)=1 and f(1)=X

We can add another twist…


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of X different colors
2. size 2 X 1 of Y different colors
3. size 3 X 1 of Z different colors

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


In this case the number of ways to construct an N X 1 rectangle = f(n) = X * f(n-1) + Y * f(n-2) + Z * f(n-3) ; with f(0)=1, f(1)=X,f(2)=X+Y

All of the above variations can be solved using Matrix Exponentiation. We just need to find the exponentiation matrix carefully.

Apart from ‘number of ways to form rectangles’, in a programming problem you could be asked to compute the number of ways to climb stairs or many other variations.
This page contains many interesting questions.

The ability to decompose a problem into its sub-problems and to compute its solution from the solution of its sub-problems is very useful in solving many Dynamic programming, Recurrance equation and Graph related problems.

If you have any doubt, feel free to leave a comment here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s