How many triplets with index (i,j,k) in an array such that i < j and j < k?

Question

Can someone give me a formula to calculate all possible triplets with index (i,j,k) in an array such that i < j and j < k?

So far I've tried to find out what is the pattern on small arrays, like this:

• Array size: 3 => number of triplets = 1
• Array size: 4 => number of triplets = 4
• Array size: 5 => number of triplets = 10

....

Answer 1

If you have $n$ indices, there are $\binom{n}{3}$ triples of distinct indices, which is what you want. Hence the answer you are looking for is $\binom{n}{3}$, also equal to $\frac{n(n-1)(n-2)}{3!} = \frac{n(n-1)(n-2)}{6}$.