The total number of pairs of records among n records is:

n(n-1)/2
  • n^2/2
  • n
  • 2n
  • 2n^2
  • n \log n
  • n!
  • n!/2
  • n(n+1)/2

There are n ways to pick the first record in the pair.

This leaves n-1 ways to pick the second record.

We consider pair (A, B) to be the same as pair (B, A).