Counting the ways to build a wall with two tile sizes [closed]

Question

You are given a set of blocks to build a panel using 3”×1” and 4.5”×1" blocks.

For structural integrity, the spaces between the blocks must not line up in adjacent rows.

There are 2 ways in which to build a 7.5”×1” panel, 2 ways to build a 7.5”×2” panel, 4 ways to build a 12”×3” panel, and 7958 ways to build a 27”×5” panel. How many different ways are there to build a 48”×10” panel?

This is what I understand so far:

with the blocks 3 x 1 and 4.5 x 1

I've used combination formula to find all possible combinations that the 2 blocks can be arranged in a panel of this size

C = choose --> C(n, k) = n!/r!(n-r)! combination of group n at r at a time

Panel: 7.5 x 1 = 2 ways -->

1 (3 x 1 block) and 1 (4.5 x 1 block) --> Only 2 blocks are used--> 2 C 1 = 2 ways

Panel: 7.5 x 2 = 2 ways

I used combination here as well

1(3 x 1 block) and 1 (4.5 x 1 block) --> 2 C 1 = 2 ways

Panel: 12 x 3 panel = 2 ways -->

2(4.5 x 1 block) and 1(3 x 1 block) --> 3 C 1 = 3 ways

0(4.5 x 1 block) and 4(3 x 1 block) --> 4 C 0 = 1 way

3 ways + 1 way = 4 ways

(This is where I get confused)

Panel 27 x 5 panel = 7958 ways

6(4.5 x 1 block) and 0(3 x 1) --> 6 C 0 = 1 way

4(4.5 x 1 block) and 3(3 x 1 block) --> 7 C 3 = 35 ways

2(4.5 x 1 block) and 6(3 x 1 block) --> 8 C 2 = 28 ways

0(4.5 x 1 block) and 9(3 x 1 block) --> 9 C 0 = 1 way

1 way + 35 ways + 28 ways + 1 way = 65 ways

As you can see here the number of ways is nowhere near 7958. What am I doing wrong here?

Also how would I find how many ways there are to construct a 48 x 10 panel? Because it's a little difficult to do it by hand especially when trying to find 7958 ways.

How would write a program to calculate an answer for the number of ways for a 7958 panel? Would it be easier to construct a program to calculate the result? Any help would be greatly appreciated.

Answer 1

I don't think the "choose" function is directly applicable, given your "the spaces between the blocks must not line up in adjacent rows" requirement. I also think this is where your analysis starts breaking down:

Panel: 12 x 3 panel = 2 ways -->

2(4.5 x 1 block) and 1(3 x 1 block) --> 3 C 1 = 3 ways

0(4.5 x 1 block) and 4(3 x 1 block) --> 4 C 0 = 1 way

3 ways + 1 way = 4 ways

...let's build some panels (1 | = 1 row, 2 -'s = 1 column):

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |      
|          |         |      |      
+---------------------------+

+---------------------------+
|      |          |         |            
|      |          |         |      
|      |          |         |      
+---------------------------+

+---------------------------+
|          |      |         |                  
|          |      |         |      
|          |      |         |      
+---------------------------+

Here we see that there are 4 different basic row types, but none of these are valid panels (they all violate the "blocks must not line up" rule). But we can use these row types to create several panels:

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |         |      |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|      |          |         |      
+---------------------------+

+---------------------------+
|      |      |      |      |
|      |      |      |      |
|          |      |         |     
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|      |          |         |
+---------------------------+

+---------------------------+
|          |         |      |      
|          |         |      |
|          |      |         |
+---------------------------+

...

But again, none of these are valid. The valid 12x3 panels are:

+---------------------------+
|      |      |      |      | 
|          |      |         |
|      |      |      |      |
+---------------------------+

+---------------------------+
|          |      |         |
|      |      |      |      |
|          |      |         |
+---------------------------+

+---------------------------+
|          |         |      |
|      |          |         |
|          |         |      |
+---------------------------+

+---------------------------+
|      |          |         |
|          |         |      |
|      |          |         |
+---------------------------+

So there are in fact 4 of them, but in this case it's just a coincidence that it matches up with what you got using the "choose" function. In terms of total panel configurations, there are quite more than 4.

Answer 2

1. Find all ways to form a single row of the given width. I call this a "row type". Example 12x3: There are 4 row types of width 12: (3 3 3 3), (4.5 4.5 3), (4.5 3 4.5), (3 4.5 4.5). I would represent these as a list of the gaps. Example: (3 6 9), (4.5 9), (4.5 7.5), (3 7.5).

2. For each of these row types, find which other row types could fit on top of it.

   Example:

   a. On (3 6 9) fits (4.5 7.5).

   b. On (4.5 9) fits (3 7.5).

   c: On (4.5 7.5) fits (3 6 9).

   d: On (3 7.5) fits (4.5 9).

3. Enumerate the ways to build stacks of the given height from these rules. Dynamic programming is applicable to this, as at each level, you only need the last row type and the number of ways to get there.

Edit: I just tried this out on my coffee break, and it works. The solution for 48x10 has 15 decimal digits, by the way.

Edit: Here is more detail of the dynamic programming part:

Your rules from step 2 translate to an array of possible neighbours. Each element of the array corresponds to a row type, and holds that row type's possible neighbouring row types' indices.

0: (2)
1: (3)
2: (0)
3: (1)

In the case of 12×3, each row type has only a single possible neighbouring row type, but in general, it can be more.

The dynamic programming starts with a single row, where each row type has exactly one way of appearing:

1 1 1 1

Then, the next row is formed by adding for each row type the number of ways that possible neighbours could have formed on the previous row. In the case of a width of 12, the result is 1 1 1 1 again. At the end, just sum up the last row.

Complexity:

• Finding the row types corresponds to enumerating the leaves of a tree; there are about (/ width 3) levels in this tree, so this takes a time of O(2^w/3) = O(2^w).

• Checking whether two row types fit takes time proportional to their length, O(w/3). Building the cross table is proportional to the square of the number of row types. This makes step 2 O(w/3·2^2w/3) = O(2^w).

• The dynamic programming takes height times the number of row types times the average number of neighbours (which I estimate to be logarithmic to the number of row types), O(h·2^w/3·w/3) = O(2^w).

As you see, this is all dominated by the number of row types, which grow exponentially with the width. Fortunately, the constant factors are rather low, so that 48×10 can be solved in a few seconds.