# Bridge building with irregular planks

Imagine you have a big rectangular pond in your back garden. You wish to build a bridge from your house in the lower left corner to the small pagoda in the top right.

You have lots of planks of length $$1$$ and $$2$$. You only wish to place planks orthogonal to the sides of the pond, and you don't want to go backwards ever. The pond is $$10\times10$$.

How many ways are there to do this?

For example:

. . . ._P
|
. . . . .
|
. . . . .
|
. . ._. .
|
H_._. . .


For a bonus, is there a generic solution for planks of length $$l_1,l_2,\dots,l_k$$?

Rather than thinking of planks as having lengths, think of them as defining certain sets of vectors. So in this case we have (1,0), (0,1), (2,0), (0,2). (Caution: if you have e.g. a plank of length 5 then you need to allow (3,4) and (4,3) as well as (5,0) and (0,5)! [EDITED to add:] No, as pointed out by another user in comments that's wrong because the question specifies orthogonal only. Though obviously you could also do it the other way if you wanted :-).)

Now we have a recurrence relation: if we write $$N(a,b)$$ for the number of ways to span a pond of size $$(a,b)$$ then we have $$N(0,0)=1$$ and $$N(a,b)=\sum N(a-x,b-y)$$ where the sum is over plank-vectors $$(x,y)$$.

For the particular case here, the table looks like this:

$$\begin{array}{r} 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ 1 & 2 & 5 & 10 & 20 & 38 & 71 & 130 & 235 & 420 & 744 \\ 2 & 5 & 14 & 32 & 71 & 149 & 304 & 604 & 1177 & 2256 & 4266 \\ 3 & 10 & 32 & 84 & 207 & 478 & 1060 & 2272 & 4744 & 9692 & 19446 \\ 5 & 20 & 71 & 207 & 556 & 1390 & 3310 & 7576 & 16807 & 36331 & 76850 \\ 8 & 38 & 149 & 478 & 1390 & 3736 & 9496 & 23080 & 54127 & 123230 & 273653 \\ 13 & 71 & 304 & 1060 & 3310 & 9496 & 25612 & 65764 & 162310 & 387635 & 900448 \\ 21 & 130 & 604 & 2272 & 7576 & 23080 & 65764 & 177688 & 459889 & 1148442 & 2782432 \\ 34 & 235 & 1177 & 4744 & 16807 & 54127 & 162310 & 459889 & 1244398 & 3240364 & 8167642 \\ 55 & 420 & 2256 & 9692 & 36331 & 123230 & 387635 & 1148442 & 3240364 & 8777612 & 22968050 \\ 89 & 744 & 4266 & 19446 & 76850 & 273653 & 900448 & 2782432 & 8167642 & 22968050 & 62271384 \end{array}$$

The number you want is in the bottom right of the array. This happens to be http://oeis.org/A036355. In general, the generating function for these things is $$\frac1{1-\sum x^{dx}y^{dy}}$$ where the sum is over plank-vectors $$(dx,dy)$$. I guess you can probably get a closed form out of that somehow.

• I was about to post the same table. :-) Mar 22 '19 at 13:42
• Why am I not surprised that the person saying that is you? :-) Mar 22 '19 at 13:49
• On my computer, the table spills over into the HNQ. Maybe just me? Mar 22 '19 at 14:13
• @GarethMcCaughan The (3,4)/(4,3) bit is wrong, and confused me for a minute before I realized what you meant. You can't place planks on an angle like that, since the question specified that planks must be "orthogonal to the sides of the pond". Mar 22 '19 at 16:28
• @Brandon_J Not just you, me too Mar 22 '19 at 19:17

My answer (using a computer program) is:

There are 8777612 ways to arrange the planks.
I solved this using a C program

#include <stdio.h>#define WIDTH   10#define DEPTH   10#define PLANK   2unsigned long long cache[DEPTH][WIDTH];unsigned long long recur(int row, int col) {    if(row >= DEPTH || col >= WIDTH)        return 0;    if(row == DEPTH-1 && col == WIDTH-1)        return 1;    if(cache[row][col] != 0)        return cache[row][col];    unsigned long long paths = 0;    for(int p = 1; p <= PLANK; p++) {        paths += recur(row + p, col);        paths += recur(row, col + p);    }    cache[row][col] = paths;    return paths;}int main(void) {    printf("Paths = %llu\n", recur(0, 0));}

Note that this is from coordinate (0,0) to (9,9) because the start and finish points are in the pond. The distance is $$9$$ in each direction. It checks out when manually counting small ponds.

This also provides a generic solution for ponds up to $$26 \times 26$$, or up to $$2^{64}-1$$ paths.
For small ponds the cache isn't necessary.

• @JonMarkPerry isn't the other answer for 11 x 11 pond? Count across the table. Mar 22 '19 at 14:49