和2元的子集

Question

我知道這不是嚴格意義上的編程問題，但計算機科學家可能知道答案。爲什麼前n個非負數的總和等於2個元素子集的數量？

Answer 1

它不是。 1 + 2 + 3 = 6.該集合中2元素子集的數量爲3.

Answer 2

所以你問的是：爲什麼0 + 1 + 2 + ... + n - 1等於n中的2個元素可以是選擇。

試想用n節點（圖中的每一個節點被連接到所有其他節點）的完整圖。然後，2元素子集的數量等於圖的邊數。

讓節點是v1, v2, ..., vn。爲了構建完整的曲線圖中，連接到v1v2, ..., vn第（n-1條邊），然後連接到v2v3, ..., 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相同的事情。