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 1In 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 colorsIn 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.