[C/C++] Project Euler #15 Counting fractions(Combination)

This problem is about calculating paths in a grid. Here is the explanation and requirements:

Problem Statement:
Given a two-dimensional grid, you need to calculate the number of distinct paths from the top-left corner to the bottom-right corner. The movement is restricted to only rightward or downward directions. The size of the grid is  \(n \times n\) , and the goal is to compute the total number of paths.

Requirements:
• Find the number of possible paths in an  \(n \times n\)  grid.
• The number of paths can be calculated using the combination formula  \(C(2n, n)\) , which is given by  \(C(2n, n) = \frac{(2n)!}{n! \times n!}\) .
• Since the numbers involved can grow very large, precise computation is necessary.

For instance, in a  \(2 \times 2\)  grid, there are exactly 6 possible paths.

 

\(2 \times 2\) grid possible paths

 

For example, in a 2x2 grid where movement is restricted to right (R) and down (D), the total number of paths can be represented as follows:

RRDD
RDRD
RDDR
DRRD
DRDR
DDRR

As shown above, there are 6 possible paths in total. Among these, if we focus only on the placement of R (right movements), the problem reduces to finding the number of ways to arrange 2 Rs in 4 positions.

This corresponds to the number of combinations for selecting 2 positions for R out of 4, which is calculated as:

\[C(4, 2) = \frac{4!}{2! \cdot 2!} = 6\]

 

Ultimately, what we need to calculate is  \(_{40}C_{20}\) . This value can be computed even without a program, but if we use a program, a 32-bit data type won’t suffice. This is because we are multiplying numbers with two digits about 20 times and dividing smaller numbers about 20 times, leading to numbers that are roughly 10 digits long or more. In fact, the result will exceed 12 digits. If we were to calculate it using simple factorials, even a 64-bit data type like long long would overflow.

While there are various techniques for calculating combinations, here we use a method of multiplying and dividing incrementally. From  n  to  n-k , the product will always include factors from  1  to  k+1 . We take advantage of this to perform the division, which allows us to calculate the combination while maintaining integer precision.

The formula used is:

\[\prod_{k=1}^{r} \frac{(n-k+1)}{k}\]

Another method involves using Pascal’s triangle, based on the principle:

\[_nC_r = ~_{n-1}C_r + _{n-1}C_{r-1}\]

However, if the size of the combination is very large, both methods may still face limitations. In some cases, modular arithmetic is required, such as when a modulus is provided, particularly with a prime modulus. In such cases, you would use an algorithm tailored for modular arithmetic.

 

grid paths

Below is a program that computes the combination  \({40}C{20}\) :

//------------------------------------------------
//    Project Euler #15 - Counting fractions
//        - by Aubrey Choi
//        - created at 2014-12-31
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void solve1()
{
    int n=40, r=1;
    long long c = 1;

    for(;r<=20;n--,r++) { c *= n; c /= r; }
    printf("Ans = %lld\n", c);
}

int main()
{
    clock_t t;

    t = clock();
    solve1();
    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);

    return 0;
}