如何获得 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 的答案。

- ACuriousCat

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。

- pjs

---

谢谢pjs，这绝对是一种聪明的查看方式！ - ACuriousCat

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。

- OmG

Answer 3

这是一个算法的数学模型，被称为二项式系数（组合）。在算法分析中，您可以使用此形式：N^k/k! 在您的代码中，您有一个无重复的情况，因此 n*(n-1)*(n-2)/3!

- Artur

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community