Ytdyklly

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 $10times10$.

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.

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 = %llun", 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.