\(S = \sum_i d_i\) とします。

\(S \geq 2\left(N-1\right)\) のとき

各部品毎に \(1\) つずつ「特別な穴」を選びます。

以下の手順により、 \(N - 1\) 個の接続用部品を順に使用します。

• 以下を \(N - 2\) 回行います。

  • 特別な穴ではない未使用の穴を \(1\) つ選びます。
  • 選んだ穴を持つ部品と連結ではない部品が持つ特別な穴のうち、未使用であるものを \(1\) つ選びます。
  • これら \(2\) つの穴を接続します。

• 最後に、未使用である \(2\) つの特別な穴を接続します。

このとき、各部品について、最後に追加された接続用部品に最も近い穴は、特別な穴となっています。

このような完成形の作り方は、

\[ \begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \times \left(N-1\right)! \end{aligned} \]

通り存在します。この方法は、各完成形について、辺の追加順に対して重複して数えていますから、この場合の答えは

\[ \begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \end{aligned} \]

です。

\(S < 2\left(N-1\right)\) のとき

このとき、接続用部品を挿し込む穴が不足している為、答えは \(0\) です。ここで、 \(\left(N \leq \right) S < 2 \left(N - 1\right)\) のとき、

\[ \begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) = 0 \end{aligned} \]

が成立しています。

以上より、答えは常に

\[ \begin{aligned} \prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \end{aligned} \]

です。