CSP-S 2024 第一轮 第12题：设有一个10个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为4的环？（

题目

设有一个 $10$ 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 $4$ 的环？

选项

• A. 120
• B. 210
• C. 630
• D. 5040

答案

C

题解

答案是 C. 630。

长度为 \(4\) 的环由 4 个不同顶点组成，分两步计数：

1. 从 \(10\) 个顶点中选出 \(4\) 个，有

\[ \binom{10}{4}=210 \] 种选法。

1. 对每组 \(4\) 个顶点，固定其中一个作为起点，其余 \(3\) 个顶点有 \(3!=6\) 种排列。但顺时针和逆时针走的是同一个环，所以共有

\[ \frac{3!}{2}=3 \] 个不同的环。

因此总数为 \[ \boxed{\binom{10}{4}\times\frac{3!}{2}=210\times3=630}. \]

注意：选出同样的 \(4\) 个顶点，可以形成不同的环，所以不能只算 \(\binom{10}{4}\)。