Sum of first n numbers and 2-element subsets [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question 开发者_开发技巧

I know it's not strictly a programming question but computer scientists might know the answer. why is the sum of the first n non-negative numbers equal to the number of 2-element subsets?

---

So what you are asking is: why is 0 + 1 + 2 + ... + n - 1 equal to the number of ways in which 2 elements out of n can be selected.

Imagine a complete graph with n nodes (every node of the graph is connected to every other node). The number of 2-element subsets is then equal to the number of edges of the graph.

Let the nodes be v1, v2, ..., vn. To construct the complete graph, connect v1 to v2, ..., vn (n-1 edges), then connect v2 to v3, ..., vn (n-2 edges), and so on up to vn that need not be connected to any more nodes. Thus the number of edges is thus (n-1) + (n-2) + ... + 0 which is exactly equal to the first sum we introduced.

A less intuitive explanation is simply to note that 0 + 1 + ... + n-1 = [(0 + n-1) + (1 + n-2) + ... + (n-1 + 0)] / 2 = n * (n - 1) / 2 and that the formula for the number of k-combinations n! / (k! * (n-k)!) = n! / (2! * (n-2)!) = (n * (n - 1)) / 2! gives the same thing for k = 2.

---

It's not. 1 + 2 + 3 = 6. The number of 2-element subsets in that set is 3.