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. :-) – Jaap Scherphuis Mar 22 at 13:42
• Why am I not surprised that the person saying that is you? :-) – Gareth McCaughan Mar 22 at 13:49
• On my computer, the table spills over into the HNQ. Maybe just me? – Brandon_J Mar 22 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". – Billy Mailman Mar 22 at 16:28
• @Brandon_J Not just you, me too – Sensoray Mar 22 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 2

unsigned 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. – Weather Vane Mar 22 at 14:49