When trying to find the number of unique pairs in $n$ elements why does the combination formula output a different value from $n(n-1)/2$

combinationscombinatoricsfactorialsequences-and-series

I was recently doing a problem on LeetCode that involved counting the number of pairs of dominoes that could be formed from a set. And I have a question about the math behind a certain section of it. So essentially if you have $N$ number of elements and need to calculate how many pairs you can form from that $N$ number of elements it seems to be the right answer to use:
$$
\frac{n(n-1)}{2}
$$
Rather than using the combination formula:
$$
\frac{n!}{r!(n-r)!}
$$
Where $r$ would equal $2$. They seemed to have different outputs, although it seemed to be correct at lower input sizes. However, once it got larger, they seemed to have different answers. Would anyone care to explain when and why to use these in certain scenarios? It seems to me they should be equivalent when setting $r = 2$, but apparently not.

  • Edit:
    Thanks for the help everybody! It turned out to be an integer overflow problem from the factorial elements of the calculation. I'm a bit rusty on my proofs, and I appreciate the everybody's explanations for how the two were equivalent as that totally makes sense!

My original function did this:

    private static int NumOfCombinations(int n, int r)
    {
       int nFac = Factorial(n);
       int rFac = Factorial(r);
       int diffFac = Factorial(n-r);
    
       return nFac / (diffFac * rFac);
    }

While my new function does this (much more efficient too):

private static int Combination(int n, int r)
{
    int rFac = Factorial(r);
    int numerator = 1;
    int nFacs = n;
    while (nFacs > n - r)
    {
        numerator *= nFacs;
        nFacs -= 1;
    }
    return numerator / rFac;
}

Best Answer

Both of these are actually equivalent. One definition often given in earlier classes is that

$$\binom n r = \frac{n!}{r!(n-r)!}$$

However, an alternative definition also arises that is at least easier to grasp for mental arithmetic: on the top, you calculate the factorial as normal ($n! = n(n-1)(n-2)\cdots$ and so on) until you have $r$ factors up there. And then you just divide that by $r!$. That is,

$$\binom n r = \frac{n(n-1)(n-2)\cdots(n-r+1)}{r!}$$

These are clearly equivalent computations: expand both $n!$ and $(n-r)!$ as products in the original definition to see the cancellations. Of course, this also means that

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

(Note that $2!=2$.)

Whatever difference between these two formulas you've been noticing has been a calculation error. Sorry to inform you.

Related Question