Program to calculate number of paths through a rectangular grid

A user at StackOverflow has problems to come up with a recursive function that computes the number of paths through a square grid of a given size. I've generalized this problem for rectangular grids and found a very elegant solution (Kotlin):

fun board(x: Int, y: Int): Int =
    if (x <= 1 || y <= 1) 1
    else board(x - 1, y) + board(x, y - 1)

fun main(args: Array<String>)
{
    var numcur = board(10, 10)
    print("$numcur")
}

If we calculate this for x = y = 1, ..., 10, we get the values 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620. A Google search shows that this sequence is known as Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2. As a comment of a user of the OEIS database shows it is indeed the solution to our problem:

The number of direct routes from my home to Granny's when Granny lives n blocks south and n blocks east of my home in Grid City. To obtain a direct route, from the 2n blocks, choose n blocks on which one travels south. For example, a(2)=6 because there are 6 direct routes: SSEE, SESE, SEES, EESS, ESES and ESSE. - Dennis P. Walsh, Oct 27 2006

Kommentare

Beliebte Posts aus diesem Blog

The Demoscene

Digital Art Natives

Autobiographical Sketch