现有一九人组，其中每人均与组中其他两人握手。记 $N$ 为可能存在的握手方式总数。我们认定两个握手方式是不同的当且仅当至少有两人仅在其中一种方式下握了手。求 $N$ 模 $1000$ 的值。
【难度】
【出处】
2012年第30届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
016
【解析】
我们将人视为顶点，顶点之间有连线表示握过手，则可生成图。我们下面分四类情况讨论：
图分为 $3$ 个长度为 $3$ 的环。 $\frac{\left( \begin{matrix}
9 \\
3 \\
\end{matrix}\right)\left( \begin{matrix}6 \\
3 \\
\end{matrix}\right)\left( \begin{matrix}3 \\
3 \\
\end{matrix}\right)}{3}{{\left( 1 \right)}^{3}}\text{=}280$
图分为 $1$ 个长度为 $3$ 的环和 $1$ 个长度为 $6$ 的环。 $\left( \begin{matrix}
9 \\
6 \\
\end{matrix}\right)\left( 1 \right)\frac{\left( 6-1 \right)}{2}\text{=504}0$
图分为 $1$ 个长度为 $4$ 的环和 $1$ 个长度为 $5$ 的环。 $\left( \begin{matrix}
9 \\
5 \\
\end{matrix}\right)\cdot \frac{4!}{2}\cdot \frac{3!}{2}=4536$
图为长度为 $9$ 的环。 $\left( \begin{matrix}
9 \\
9 \\
\end{matrix}\right)\cdot \frac{8!}{2}=20160$
故一共有 $280+5040+4536+20160=30016\to 016$
图分为 $3$ 个长度为 $3$ 的环。 $\frac{\left( \begin{matrix}
9 \\
3 \\
\end{matrix}\right)\left( \begin{matrix}6 \\
3 \\
\end{matrix}\right)\left( \begin{matrix}3 \\
3 \\
\end{matrix}\right)}{3}{{\left( 1 \right)}^{3}}\text{=}280$
图分为 $1$ 个长度为 $3$ 的环和 $1$ 个长度为 $6$ 的环。 $\left( \begin{matrix}
9 \\
6 \\
\end{matrix}\right)\left( 1 \right)\frac{\left( 6-1 \right)}{2}\text{=504}0$
图分为 $1$ 个长度为 $4$ 的环和 $1$ 个长度为 $5$ 的环。 $\left( \begin{matrix}
9 \\
5 \\
\end{matrix}\right)\cdot \frac{4!}{2}\cdot \frac{3!}{2}=4536$
图为长度为 $9$ 的环。 $\left( \begin{matrix}
9 \\
9 \\
\end{matrix}\right)\cdot \frac{8!}{2}=20160$
故一共有 $280+5040+4536+20160=30016\to 016$
答案
解析
备注
