Find LHS for Induction : Total number of triples selected from N items = N(N-1)(N-2)/6

Question

How do I find the LHS for finding the total number of sets of k items each selected from N items. Order does not matter.

For e.g. 1+2+3+...+n = n(n+1)/2

How do I find the LHS for my query? RHS is n(n-1)(n-2)/6 and the question is "Show that total number of triples selected from N items is precisely equal to N(N-1)(N-2)/6".

Answer 1

Total number of k-tuples selected from n items is the binomial coefficient

$$ C^k_n = \frac{n!}{k!(n-k)!}$$.

In your case $k=3$, so you get:

$$C^3_n = \frac{n!}{3!(n-3)!} = \frac{n(n-1)(n-2)(n-3)!}{6(n-3)!} = \frac{n(n-1)(n-2)}{6}$$