前n个数和2个元素子集的和

Question

我知道这不是一个严格的编程问题,但计算机科学家可能知道答案.为什么前n个非负数的总和等于2个元素子集的数量？

Answer 1

所以你要问的是:为什么0 + 1 + 2 + ... + n - 1等于n可以选择2个元素的方式的数量.

想象一下包含n节点的完整图形(图形的每个节点都连接到每个其他节点).然后,2元素子集的数量等于图形的边缘数量.

让节点成为v1, v2, ..., vn.要构建完整的图形,请连接v1到v2, ..., vn(n-1条边),然后连接v2到v3, ..., vn(n-2条边),依此类推,直到vn不需要连接到任何更多节点.因此,边缘的数量(n-1) + (n-2) + ... + 0恰好等于我们引入的第一个总和.

一个不太直观的解释只是要注意,0 + 1 + ... + n-1 = [(0 + n-1) + (1 + n-2) + ... + (n-1 + 0)] / 2 = n * (n - 1) / 2并且k组合数的公式n! / (k! * (n-k)!) = n! / (2! * (n-2)!) = (n * (n - 1)) / 2!给出相同的东西k = 2.