点图中的三角形

在用点组成的网格图中，可以构建出多少个三角形呢? 要找到正确答案，我们需要面临两个挑战——真实并准确地数到每个三角形，并且避免把任何不构成三角形的三个点算入总个数. 在今日挑战中，点阵中的部分点可以形成三角形. 如果你想看一个简单问题的解决方法，请继续阅读；或者你可以直接跳到今日挑战.

让我们数一数，当三角形的每个顶点都是下图中的点时，可以形成多少个三角形.

上图中共有9个点，要形成一个三角形，我们需要其中3个点作为顶点. 从9个点中选择3个点是一种组合，因为我们选择它们的顺序不会改变它们形成的三角形. 从n个项的集合中抽取k个项的组合数为二项式系数，因此在图中有 个组合.

然而，并不是所有三个点的组合都能构成三角形. 如果三个顶点都落在同一水平线或竖直线上，那我们得到的是一条直线而非三角形. 所以我们需要注意如何计数. 接下来需要进行分类讨论.

如果三个顶点都落在同一水平线上，则有种情况 ，同理，如果三个顶点都落在同一竖直线上，则也有种情况 ，因此能构成三角形的情况总共有种.

这是从所有情况中除去不能构成三角形的情况，可谓是间接法，那么能直接计算吗？可以.

因为我们只有一条由点构成的竖直线和一条由点构成的水平线，所以我们形成的任何三角形都必须在一条直线上有2个顶点，同时在另一条直线上有1个顶点. 注意，中间的点在交点处，既是竖直线的一部分，也是水平线的一部分.

因此我们还可以根据中间的点来分类不同的情况.

首先，让我们计算不包括中间点作为顶点的三角形. 如果一个三角形在水平线上有2个顶点，它们可以是4个点. 所以有种选择这些点的方法. 第三个顶点可以是竖直线上的4个点中的任何一个，所以总共有个这样的三角形.

由于这个点图是对称的，所以如果一个三角形在竖直线上有两个顶点，在水平线上有第三个顶点，那么也有24个这样的三角形.

现在，我们计算包含中间点作为顶点的三角形.其他顶点不能同时在水平线或垂直线上，所以每条线上必须有一个顶点.从水平线上和竖直线上分别取一个点都有4种选择，所以共有个三角形.

每个三角形包含或不包含中间的点作为顶点，所以在这两种情况下，我们计算了所有可能形成的三角形. 也就是说此点图中可能形成的三角形共有个.

今日挑战中的点图更大，也不对称. 你还能用分类讨论的方法来求三角形的个数吗?