最初のn個の数値と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とします。完全なグラフを作成するには、を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について同じことを与えます。