Lattice Paths Part 3 (Combinations)

Starting in the top left corner of a 2 x 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 x 20 grid, or any N x N grid?

--

This is the last of the three-part series article about explaining how you could have arrived at the solution yourself in solving the Lattice Paths Problem. If you haven't tried it yet, do it first. I do not intend to deny you of your epiphany moment!

Note: All implementations are written in C/C++.

--

Combination (nCr)

We all learned about Factorials, Permutations, and Combinations in College. This article will be a quick refresher and the final solution to the given problem.

Terminologies

Let's start by defining some terminologies:

Factorial:

A factorial is a product of an integer and all the integer below it.

For example, the factorial of 4 (also denoted as 4!) is 4 x 3 x 2 x 1 = 24. 

Factorial of (0!) = 1 (Note: The proof will not be discussed here).

Permutation:

The number of ways you can represent a subset of the items in unique orders. For example, the word CAT can be arranged in six (6) ways, if subset = all items.

• CAT
• CTA
• ACT
• ATC
• TAC
• TCA

Let's see at close inspection if we change the subset to 2, for CAT.

• CA
• CT
• AC
• AT
• TA
• TC

Permutation is denoted as nPr, where n is the total number of items, and r is the number to represent. Based on the examples and definitions above, we can express nPr as n! / (n - r)!.

Combination:

Combination is similar to Permutation except for the fact that we are counting subsets with similar members as one. For the CAT example, the number of ways we can represent it in a combination, if subset = all items is one (1).

Let's see at close inspection if we change the subset to 2, for CAT.

• CA, AC are counted as 1
• CT, TC are counted as 1
• AT, TA are counted as 1

Combination is denoted as nCr, where n is the total number of sites, and r is the number to represent. Based on the examples and definitions of Combination above, we can expressed it as nCr = n! / r! (n - r)!

Finding n and r and choosing between Permutation and Combination:

In the first part of the article, we tried to Brute Force our solution to the problem. The function countRouteBruteForce(), displays the string combinations of Right and Down movements within a N x N grid. Based on our observation, we can inductively conclude that the number of movements to Traverse (0, 0) to (N, N) is always 2N.

Let's take a look at the 3 x 3 grid and represent Down and Right movements as letters a - f, for each position in the 2N string:

• a b c d e f
• where a to f can be either right or down.

Now think about this, there can never be four (4) downs or four (rights) in the 3 x 3 matrix as it will exceed the grid. Therefore, there are always 3 downs and 3 rights in every traversal string. If this is the case then our (r) is N, because the other half of the string combination where there are 4 downs and 2 rights, and so on and so forth are discarded.

At this point, we've already established that n = 2N and r = N. The next task is to determine whether to use the Permutation or Combination Formula.

Let's assign values to letters a to f

• a = right
• b = right
• c = right
• d = down
• e = down
• f = down

Now let's see if we need to count abcdef and acbfed as two separate items or just one. After assigning values, we can confidently say that we need to count these two (2) as one, therefore the formula that we need is Combination.

The Solution:

Now let's apply the Combination formula to get the number of routes or Routes(N) for any given N x N grid.

• nCr = n! / (r! (n - r)!)
• nCr = (2N)! / (N! (2N - N)!) = (2N)! / (N! x N!)
• N = 20
• nCr = 40! / (20! x 20!)
• nCr = 137,846,528,820 = Routes (N)

If we translate this formula directly to C/C++ or to any programming language, the result will overflow as factorials result in ridiculously large values even for small values N. Let's simply the formula to the following:

• 2N! can be written as 2N x (2N - 1) x .... x 2 x 1 or 2N x (2N - 1) x .... x (n + 1) x N!
• Cancel out N! from the numerator and denominator

Then we get:

• { 2N x (2N - 1) x .... x (n + 1) } / { n x (n - 1) x ... x 2 x 1 }

Let's now translate this to code and call it countRouteCombination()

long double countRouteCombination(void)
{
    int i;
    long double total = 1, NN = MAX_SIDES * 2 + 1;

    for (i = 1; i <= MAX_SIDES; i++)
    {
        total *= (NN - i) / i;
    }

    return total;
}

Important Note: If you invoke a single line function factorial in your program, it doesn't make it an O(1) Time Complexity Solution, as factorials are implemented with O(N) Time complexity. Implementing the formula of nCr directly gives you O(3N) Time complexity.

There you have it, a solution with a Time complexity of O(N) and Space complexity of O(1).