Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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

- 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.
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search