How to formulate this type of counting problem?

20 Views Asked by At

Let's say there are three variables $i, j, k$ such that all of them lie between $[0, n)$

Now my question is how can I formulate the number of triplets that I can form with these three variables such that it follows these two conditions: $i < j$ and $j < k$

I wrote a sample program taking $n$ as $10$

n = 10
count = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i < j and j < k:
                count += 1

The count for $n=10$ is 120.

I can run through all the cases and come up with the final solution on the paper, but for some reason, I am not able to generalize this for any given value of $n$

1

There are 1 best solutions below

0
On BEST ANSWER

Clearly $i,j,k$ have to be distinct. If we choose any three distinct numbers from $[0,n)$, they must be $i,j,k$ in ascending order. This establishes a bijection between the number of admissible triples $(i,j,k)$ and the number of ways to choose three items from $n$, so the final answer is $\binom n3$.