Counting Patterns in Stacking Bricks

Date: 01/04/2009 at 00:44:50
From: Matth
Subject: arranging bricks

I have a number of bricks which are each 3 units long, 1 unit deep 
and 1 unit wide.  I want to stack them in a tower 3 units wide, 1 
unit deep and 10 units high.  How many ways can that be done? 

I have got 19 as my answer and 28 is the correct answer.  I don't 
know how?

First I got 6 combinations with arranging the bricks in 2 groups of 3 
vertically and 2 groups of 2 horizontally.  Next I got 4 combinations
with arranging the bricks in 3 groups of 3 vertically and 1
horizontally.  Then I got 8 with using 3 vertically and 7
horizontally.  I also got 1 with using 10 horizontally.  So 6 + 4 + 8
+ 1 = 19.  I cannot get the remaining 9 combinations.

Date: 01/04/2009 at 03:58:02
From: Doctor Greenie
Subject: Re: arranging bricks

Hi, Matth --

You found the combinations using 2 groups of 3 vertically if the 
remaining 4 bricks are in 2 groups of 2, but you overlooked two other 
possibilities with 2 groups of 3 vertically--the remaining 4 bricks
can be in a group of 3 and a single, or in a group of 2 and 2 singles.

You can get the final answer of 28 if you find the correct numbers 
of ways to get combinations of those types.  However, you will find 
it quite a bit more difficult to count the numbers of these 
combinations.

While your approach to the problem using the different possible 
combinations of vertical and horizontal groups is good, there is 
another approach to problems of this type which makes it easier to 
find the answer--especially if, in an example like yours, we want 
to find the number of ways if the tower is to be 20 or 100 bricks 
high instead of 10.

We can solve problems like this using recursive formulas.  That is, 
we can find a pattern for the number of ways to build a tower "k" 
bricks high in terms of the numbers of ways to build shorter towers.

Here is how the analysis might go for your particular problem.

(1) If the tower is only 1 brick high, then there is clearly only 1 
way to build it--1 horizontal brick.

  N(1) = 1

(2) If the tower is 2 bricks high, there is still only 1 way to 
build it--2 horizontal bricks.

  N(2) = 1

(3) If the tower is 3 bricks high, then there are 2 ways to build 
it--3 horizontal bricks, or 3 vertical bricks.

  N(3) = 2

Now, for a tower 4 bricks high, let's think about the ways we can 
"finish" building the tower.  We can either have a tower 3 bricks 
high and finish with a horizontal brick; or we can have a tower 1 
brick high and finish with 3 vertical bricks.

The number of ways we can have a tower 3 bricks high and finish with 
a horizontal brick is the number of ways to build a tower 3 bricks 
high:  N(3) = 2

And the number of ways we can have a tower 1 brick high and finish 
with 3 vertical bricks is the number of ways to build a tower 1 brick 
high:  N(1) = 1

And so the total number of ways to build a tower 4 bricks high is

  N(4) = N(3) + N(1) = 2+1 = 3

And next, for finishing a tower 5 bricks high, we can either have a 
tower 4 bricks high and finish with a horizontal brick; or we can 
have a tower 2 bricks high and finish with 3 vertical bricks.

The number of ways we can have a tower 4 bricks high and finish with 
a horizontal brick is the number of ways to build a tower 4 bricks 
high:  N(4) = 3

And the number of ways we can have a tower 2 bricks high and finish 
with 3 vertical bricks is the number of ways to build a tower 2 
bricks high:  N(2) = 1

And so the total number of ways to build a tower 5 bricks high is

  N(5) = N(4) + N(2) = 3+1 = 4

The analysis will be the same for higher towers.  We can see that, 
for a tower "k" bricks high, the number of ways to build it is

  N(k) = N(k-1) + N(k-3)

And so we can form a "recursive" formula for finding the number of 
ways to build a tower k bricks high:

  N(1) = 1
  N(2) = 1
  N(3) = 2
  for k > 3, N(k) = N(k-1) + N(k-3)

We can use this recursive formula to find the number of ways to 
build the tower 10 bricks high:

  N(1) = 1
  N(2) = 1
  N(3) = 2
  N(4) = N(3)+N(1) = 2+1 = 3
  N(5) = N(4)+N(2) = 3+1 = 4
  N(6) = N(5)+N(3) = 4+2 = 6
  N(7) = N(6)+N(4) = 6+3 = 9
  N(8) = N(7)+N(5) = 9+4 = 13
  N(9) = N(8)+N(6) = 13+6 = 19
  N(10) = N(9)+N(7) = 19+9 = 28

I hope this helps; and I hope you find it as fascinating as I did 
when I first saw it at about your age....

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/04/2009 at 08:14:25
From: Matth
Subject: Thank you (arranging bricks)

Thanks very much for that help.  I was struggling with it for a long 
time.  Thanks again.