公式解説にある \(f(S)\)、つまり \(S\subseteq V\) を頂点集合とする木の個数は、行列木定理(ラプラシアン行列)を使わなくても求めることができます。 具体的には、

\[ f(S) = \begin{cases} 1 & (\text{if }|S| \leq 1) \\ \displaystyle \frac{1}{2(|S|-1)} \sum_{T \subset S} f(T) f(S \setminus T) \mathcal{E}(T, S \setminus T) & (\text{otherwise}) \end{cases} \]

とすればよいです。 ここで、互いに素な頂点集合 \(U, W\) に対して \(\mathcal{E}(U, W)\) は \(U\) の頂点と \(W\) の頂点を結ぶ辺の個数を表し、

\[ \mathcal{E}(U, W) = e(U \cup W) - e(U) - e(W) \]

と計算できます。 ただし、頂点集合 \(U\) に対して、\(e(U)\) は \(U\) に含まれるいずれか 2 頂点を結ぶ辺の本数です。

すべての頂点集合 \(U\) に対して \(e(U)\) を合計 \(O(N^2 2^N)\) 時間で前計算することによって、 すべての頂点集合 \(S\) に対して \(f(S)\) を合計 \(O(3^N)\) 時間で計算することができます。