Is it correct to evaluate combinations of two as sum?

Question

I've recently had a look to a problem solution that puzzles me. ANd Ican't make up my mind in order to explain myself why it seems actually to work.

Consider having N unique numbers and find all possible combinations of 2 for these N numbers (without repetition)

i.e. how many distinct couples from a population of distinct subject without repetition

I remember this is expressed as C(N,2) = N!/(N-2)!*2!

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

The proposed solution was SUMMATION for i=0 to N-1 of i

$$\sum_{i=0}^{n-1} i $$

(sorry but I dont know how to express summation here)

Testing the problem using some PHP scripting was successful :

function fact($num){
  $factorial = 1;
  for ($x=$num; $x>=1; $x--) 
  {
    $factorial = $factorial * $x;
    }

    return $factorial;
}


for($value=0; $value<=100; $value++){
  $sum = 0;
   for($i=0;$i<$value;$i++){
    $sum = $sum +$i;
        }

        $combinations = fact($value)/(2*fact($value-2));

    echo "Value: $value , Sum: $sum, Comb: $combinations".PHP_EOL;
}

Then I remembered that the SUM of the first N integers can be expressed as N(N+1)/2 , so considering N-1 that would be the same as C(N,2) = N(N-1)/2

Found a Math demonstration.

$$\sum_{i=0}^{n-1} i = \frac{(n)(n-1)}{2} = \frac{n!}{(n-2)!2!} = {n \choose 2}$$

What I'd like now (the question is) : to figure out in my mind (representation) why this summation would be the same of looking for combinations of two.... hope the aim of this question make sense

Answer 1

It is indeed. In fact, that is how Ibn al-Banna al-Marrakushi al-Azdi derived the formula.

Consider the set $S = \{1, 2, 3, \ldots, n\}$. By definition, $\binom{n}{2}$ is the number of subsets of $S$ with two elements. We count two-element subsets whose least element was $k$. If $k = 1$, there are $n - 1$ such subsets since the larger element must be selected from $\{2, 3, \ldots, n\}$. If $k = 2$, there are $n - 2$ such subsets, there are $n - 2$ since the larger element must be selected from $\{3, 4, \ldots, n\}$. In general, if $k = m$, there are $n - m$ such subsets since the larger element must be selected from $\{m + 1, m + 2, \ldots, n\}$. Hence, the number of subsets of a two-element set is $$\binom{n}{2} = \sum_{k = 1}^{n} (n - k) = \sum_{k = 0}^{n - 1} k = \sum_{k = 1}^{n - 1} k$$

Source: Victor J. Katz, A History of Mathematics: An Introduction

The argument above is based on Katz's description of al-Banna's argument. I do not know al-Banna's precise argument.

Answer 2

To choose two numbers from $\{1,2,\ldots,n\}$, pick the larger $l$ of you two numbers first, then there remain $l-1$ choices for the smaller number; all in all there are $\sum_{l=1}^n(l-1)=\sum_{i=0}^{n-1}i$ choices possible.

This is by the way the result that on MathOverflow has the top-voted proof without words at the relevant question.

Answer 3

Set-up all $N$ items in a row and give them numbers from $1$ to $N$.

Pick the first item – you can't pair it with any earlier item, because there is no earlier items → $0$ possibilities.

Pick the second item – you can pair it with exactly one earlier item → $1$ possibility.

Pick the third item – you can pair it either with the first item or with the second one → $2$ possibilities.

Pick the $i$-th item – you can pair it with any item from $1$ through $(i-1)$ → $(i-1)$ possibilities.

Pick the $N$-th item – you can pair it with any item from $1$ through $(N-1)$ → $(N-1)$ possibilities.

Hence the number of possible unordered pairs is $$\sum\limits_{i=1}^N(i-1) = \sum\limits_{i=0}^{N-1}i$$