Google has kicked off their 2008 Treasure Hunt, which looks like it's going to be a four-part series of short puzzles:

designed to test yer problem-solving skills in computer science, networking, and low-level UNIX trivia.

The first puzzle has already expired, and while there is a link to it, I'll reprise it here.

My Transcription

The playing field is a rectangular matrix with R rows and C columns. Place a marker in the upper left corner, labeled [1,1].  Your goal is to move the marker from that position to the lower right corner, labeled [R,C]. If the marker is only allowed to move one square at a time, and only allowed to move directly down or directly to the right, how many unique paths are there between the start and the destination?

Google will generate an instance of the problem for you, with values of R and C that seem to vary between 30 and 70. Once you provide the solution, in theory it will tell you whether your answer is correct, although I had some trouble in that area. (Warning: if you lose your confirmation number, your confirmation number is lost!)

Notes

This would be a nice warm-up problem for an algorithms class. There are a few interesting aspects to the problem. First - finding the exact answer. Second, providing a concise definition of the algorithm used to calculate the answer. Third - doing so in as efficient a manner as possible.

Try to see if you can solve this for values 56 and 43.  If you can come up with an implementation you're proud of in the language of your choice, post it as a comment.