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".

score 0 · Accepted Answer · answered Dec 06 '15 at 11:16

0

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}$$

answered Dec 06 '15 at 11:16

Petar Ivanov

967

Thank you so much. It was a bit foolish of me to try to find the LHS for the given RHS. – Chandan Pednekar Dec 06 '15 at 12:00

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

1 Answers1