Integer powers arising from a loop count

Here’s a simple function that counts number of times through a double loop:

function count_ops(n) {
  let cnt = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // Do something symmetric in i and j
      cnt++;
    }
  }
  return cnt;
}

Let’s try it for the first 16 integers:

d3.range(16).map((n) => count_ops(n))

Hmm… Those numbers look familiar. In fact, we see the positive integers in that list along the second diagonal of Pascal’s triangle:

pascals_triangle

That suggests that these numbers are exactly \[{{n}\choose{2}}.\]

import { pascals_triangle } from "6fe4d0894b6a9673"