# Project Euler: Lattice paths0919

Project Euler is a series of exciting programming problems that often have a mathematical background. the problems are often set up in such a way that you have to develop sophisticated algorithms to reach the goal in a reasonable runtime. today we solve problem 15: Lattice paths, where you get to the solution with simple combinatorial means.

The question is as follows:

„Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?“

The problem can also be formulated differently: What is sought is the power of the subset of all paths

$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$

This is a simple combinatorial problem, where we use the urn model (without putting it back and without considering the order). We are now interested in exactly those paths for which $$R$$ and $$D$$ occur exactly the same number of times, so for all possible combinations:

$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$

For $$n=20$$ we get:

$$\frac{(40)!}{20!\cdot 20!} = 137846528820.$$

We can extend the problem to non-square grids. The following solution implements a calculation in PHP with the help of bcmath with a runtime of $$O(n)$$ with the input format "Number of test cases, $$n_1$$ $$m_1$$ , ...":

47bb78215ee0531a787bb5034652eaf4

By the way, all problems of the Euler Project can be solved online on the recommended page HackerRank.

Back