Fibonacci

Paths and patterns

In the introduction we have studied the following two problems:



Problem 1: I want to build a stone path. To that end I have at my disposal two kinds of stones. Square stones (size 1x1) and rectangular stones (size 1x2). The path width is equal to the width of a 1x1 stone. How many different paths (patterns) of length  n can be build with these two kinds of stones?

Problem 2: I want to build a path with stones of size 1x2. The width of the path is equal to the longest side of a 1x2 stone. How many different paths of length  n can we build with these stones?

Let us enumerate some more problems of this kind:



Problem 3: I want to build a linear stone path. To that end I have at my disposal red and green square stones. How many different paths (patterns) of length  n can be build with these stones if the path may not contain adjacent red stones?

Problem 4: How many different paths of length  n can be build in case of problem 3 if the last stone has to end where the first stone starts, i.e. if the stones are put in a circle around a pond?

Problem 5: I want to build a linear stone path. To that end I have at my disposal red and green square stones. How many different paths of length  n can be build with these stones if it is not allowed to have three consecutive stones of the same color?

Problem 6: I want to build a stone path. The stones are placed in a row. To that end I have at my disposal red and green square stones. How many different paths of length  n can be build with these stones if each stone has an adjacent stone of the same color?

Problem 7: I want to build a stone path. The stones are placed in a row. I have at my disposal stones of every length, with the exception of square stones. How many different paths of length  n can be build with these stones?

Solution of problem 3:
Let a_n be the number of paths of length n, and r_n be number of paths that end with a red stone and g_n the number of paths that end with a green stone. Now add one stone to all possible rows of length n. The r_n paths with a last red stone are supplemented by a green stone, and the g_n paths with a last green stone are supplemented by a red or green stone. So, r_n+1 = g_n and g_n+1 = g_n + r_n (= a_n). Substitution shows g_n+1 = g_n + g_n-1 (= a_n), thus a_n = a_n-1 + a_n-2.   a₁ = 2,   a₂ = 3,   thus a_n = F_n+2.

Solution of problem 4:
Of all F_n+2 solutions of problem 3 we have to eliminate those solutions with a starting and ending red stone.
Between a starting and ending stone there are F_(n-4)+2 solutions, thus the number of paths is
F_n+2 - F_n-2 = F_n+1 + F_n - F_n-2 = F_n+1 + F_n-1 = L_n.

Solution of problem 5:
Again, a_n is the number of paths of lengt n. If we were allowed to extend the path without restrictions to a path of length n+1, then the number of different paths is 2a_n. From these 2a_n possibilities we have to exclude those paths that end with the combinations green, red, red, red or red, green, green, green. There are a_n-2 paths of this sort. Thus a_n+1 = 2a_n - a_n-2 = a_n + a_n-1. a₁ = 2, a₂ = 4, ergo a_n = 2F_n+1.

Solution of problem 7:
We will show (by induction) that the number of paths of length n is F_n-1.
The hypothesis is true for n=1, for the number of paths of length 1 is 0 = F₀.
Now suppose that we have allready shown that the hypothesis is correct for all n<N (where N is a positive integer larger than 1). We will show that the statement is correct for n=N.
Regard a path of length N. If the last laid stone has length k (>1), then the part of the path before the last stone can be build in F_N-k-1 ways (according to the induction hypothesis). The last stone has length N,N-1,N-2,...,3 or 2. The corresponding parts before the last stone can be build in 1,F₀,F₁,...,F_N-4 and F_N-3 ways.
In total there are 1 + F₀ + F₁ + ... + F_N-4 + F_N-3 = F_N-1 {see here} ways. Thus the statement is also correct for n=N, en therefore the number of paths of length n is F_n-1.

Solution of problem 6:
In problem 7 the laid stonen will be colored alternatively with a red and a green color. This can be done in two ways (dependent on the color of the first stone). So the number of colored paths of length n is then 2F_n-1. Next, we will break the stones into square stones. The result in paths which fulfil the demands of problem 6. Thus the number of possible paths of problem 6 is 2F_n-1.