如何获得n(n-1)(n-2) /6的结果

Question

在我的Python中，这个问题要求在运行以下代码之后证明x的值：

x = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            x += 1

我能看到的是：

i = 0;  j=1;  k=2:  from 2 to n, x+=1, (n-2) times 1
i = 1;  j=2;  k=3:  from 3 to n, x+=1, (n-3) times 1
...
i=n-3;  j=n-2; k=n-1: from n-1 to n, x+=1, just 1
i=n-2;  j=n-1; k=n doesn't add 1

因此，x似乎是(n-2) + (n-3) +.+ 1的级数之和。我不知道如何找到n(n-1)(n-2)/6的答案。

Answer 1

查看这一点的一种方法是，您有n值和三个嵌套循环，它们被构造为具有不重叠的范围。因此，可能的迭代次数等于从n项中选择三个唯一值的方法的数量，或者n choose 3 = n!/(3!(n-3)!) = n(n-1)(n-2)/3*2*1 = n(n-1)(n-2)/6。

Answer 2

只需将for循环编写为sigma：S = sum_{i=1}^n sum_{j=i+1}^n sum_{k = j + 1}^n (1)即可。

尝试将和从内部扩展到外部：S = sum_{i=1}^n sum_{j=i+1}^n (n - j) = sum_{i=1}^n n(n-i) - ((i+1) + (i+2) + ... + n) = sum_{i=1}^n n(n-i) - ( 1+2+...+n - (1+2+...+i)) = sum_{i=1}^n n(n-i) -(n(n+1)/2 - i(i+1)/2) = sum_{i=1}^n n(n+1)/2 + i(i+1)/2 - n*i = n^2(n+1)/2 + sum_{i=1}^n (i^2/2 + i/2 - n*i)。如果打开这个和并简化它(很简单)，您将得到S = n(n-1)(n-2)/6。