algorithm - Counting the ways to build a wall with two tile sizes -

algorithm - Counting the ways to build a wall with two tile sizes -

you given set of blocks build panel using 3”×1” , 4.5”×1" blocks.

for structural integrity, spaces between blocks must not line in adjacent rows.

there 2 ways in build 7.5”×1” panel, 2 ways build 7.5”×2” panel, 4 ways build 12”×3” panel, , 7958 ways build 27”×5” panel. how many different ways there build 48”×10” panel?

this understand far:

with blocks 3 x 1 , 4.5 x 1

i've used combination formula find possible combinations 2 blocks can arranged in panel of size

c = take --> c(n, k) = n!/r!(n-r)! combination of grouping n @ r @ time

panel: 7.5 x 1 = 2 ways -->

1 (3 x 1 block) , 1 (4.5 x 1 block) --> 2 blocks used--> 2 c 1 = 2 ways

panel: 7.5 x 2 = 2 ways

i used combination here well

1(3 x 1 block) , 1 (4.5 x 1 block) --> 2 c 1 = 2 ways

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

2(4.5 x 1 block) , 1(3 x 1 block) --> 3 c 1 = 3 ways

0(4.5 x 1 block) , 4(3 x 1 block) --> 4 c 0 = 1 way

3 ways + 1 way = 4 ways

(this confused)

panel 27 x 5 panel = 7958 ways

6(4.5 x 1 block) , 0(3 x 1) --> 6 c 0 = 1 way

4(4.5 x 1 block) , 3(3 x 1 block) --> 7 c 3 = 35 ways

2(4.5 x 1 block) , 6(3 x 1 block) --> 8 c 2 = 28 ways

0(4.5 x 1 block) , 9(3 x 1 block) --> 9 c 0 = 1 way

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

as can see here number of ways near 7958. doing wrong here?

also how find how many ways there build 48 x 10 panel? because it's little hard hand when trying find 7958 ways.

how write programme calculate reply number of ways 7958 panel? easier build programme calculate result? help appreciated.

here's solution in java, of array length checking etc little messy i'm sure can refine pretty easily.

in case, hope helps demonstrate how algorithm works :-)

import java.util.arrays; public class puzzle { // initial solve phone call public static int solve(int width, int height) { // double widths can utilize integers (6x1 , 9x1) int[] prev = {-1}; // create sure don't collisions on first layer homecoming solve(prev, new int[0], width * 2, height); } // build current layer recursively given previous layer , current layer private static int solve(int[] prev, int[] current, int width, int remaining) { // check whether have valid frame if(remaining == 0) homecoming 1; if(current.length > 0) { // check overflows if(current[current.length - 1] > width) homecoming 0; // check aligned gaps for(int = 0; < prev.length; i++) if(prev[i] < width) if(current[current.length - 1] == prev[i]) homecoming 0; // if have finish valid layer if(current[current.length - 1] == width) homecoming solve(current, new int[0], width, remaining - 1); } // seek adding 6x1 int total = 0; int[] newcurrent = arrays.copyof(current, current.length + 1); if(current.length > 0) newcurrent[newcurrent.length - 1] = current[current.length - 1] + 6; else newcurrent[0] = 6; total += solve(prev, newcurrent, width, remaining); // seek adding 9x1 if(current.length > 0) newcurrent[newcurrent.length - 1] = current[current.length - 1] + 9; else newcurrent[0] = 9; total += solve(prev, newcurrent, width, remaining); homecoming total; } // main method public static void main(string[] args) { // e.g. 27x5, outputs 7958 system.out.println(puzzle.solve(27, 5)); } }

algorithm combinations combinatorics tiling