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.