Suppose we want to build a brick wall out of the usual size of a brick which has a length of 2 units and a height of 1 unit.
If our wall is to be 2 units tall, we can build our wall in a number of different ways depending on how long we want to build it. Our problem here is to find the number of ways that we can build a 10 units long wall.
Use the canvas here to study the problem:
We may start solving the problem by arranging the bricks for a 2 x 1 rectangle first.
How many possible ways can they be laid?
Next, look at the 2 x 2 construction.
How many arrangements are possible?
Now try 2 x 3 arrangements.
Before we work our way up to the 2 x 10. Let’s try to see if any particular pattern starting to emerge?
The tricky pattern to spot is that each total on the right is the sum of the previous two totals.
- 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
You may have heard of the Fibonacci numbers will notice that the totals are the Fibonacci sequence, starting at 1, 2, …
So by following the Fibonacci Sequence, for the 10-unit long wall; there are 89 possible ways to arrange the bricks
You may read more about Fibonacci Numbers on Mathigon
We may wonder in how many different ways can we build an “n” unit-long wall.
In fact, there is a formula for finding any Fibonacci number without having to add up all the previous ones.
If we go back to the first question, for the 10-unit-long wall;
the number with 5 pairs lengthwise and no slabs across the path (just 1 way)= 5 choose 5
the number with 4 pairs lengthwise and 2 across (15 ways)= 6 choose 4
the number with 3 pairs lengthwise and 4 across (35 ways)= 7 choose 3
the number with 2 pairs lengthwise and 6 across (28 ways)= 8 choose 2
the number with one pair lengthwise and 8 across (9 ways) = 9 choose 1
and the number with no pairs lengthwise and all 10 across (1 way) = 10 choose 0
So the total number of ways is
C(10,0) + C(9,1) + C(8,2) + C(7,3) + C(6,4) + C(5,5)
1 + 9 + 28 + 35 + 15 + 1 = 89
We may see these numbers on the Pascal Triangle in a diagonal format.
So for n unit long wall, we can use the combination idea to choose the lengthwise bricks from a total of n bricks.
The total number of ways:
C(n,0) + C(n-1,1)+ C(n-2,2)+ C(n-3,3)+ C(n-4,4) ...+ C(n,r) where r cannot be bigger than n
We can try our latest discovery for a 12 units long wall;
With Fibonacci sequence; 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
With the Combination method;
C(12,0) + C(11,1) + C(10,2) + C(9,3) + C(8,4) + C(7,5) + C(6,6) >>
1 + 11 + 45 + 84 + 70 + 21 + 1 = 233