ウォーク全体を長さ \(2\) の節に分けます。例えば、\(S \rightarrow T \rightarrow U \rightarrow V \rightarrow S\) を二つの節 \(S \rightarrow T \rightarrow U\) と \(U \rightarrow V \rightarrow S\) の連結とみなします。C4 は二部グラフであるため、節は \(8\) 種類しか存在しません。それらを以下の三区分に分類します。

• \(T\) 通過型: \(S \rightarrow T \rightarrow U\), \(U \rightarrow T \rightarrow S\)
• \(V\) 通過型: \(S \rightarrow V \rightarrow U\), \(U \rightarrow V \rightarrow S\).
• 回帰型: \(S \rightarrow T \rightarrow S\), \(S \rightarrow V \rightarrow S\), \(U \rightarrow T \rightarrow U\), \(U \rightarrow V \rightarrow U\)

\(T\) 通過型の節の数（\(i\) とします）と \(V\) 通過型の節の数（\(j\) とします）を固定しましょう。すると、可能なウォークの数は以下の値の積となります。

（ここで \(C(x, y) :=\binom{x+y}{x}\) と表記します。すなわち \(C(x, y)\) は \(x\) 個のものと \(y\) 個のものを並べる方法の数です。\(C(x, y, z)\) も同様に定義します。無効な引数に対する値は \(0\) とします）

• まず、\(T\) 通過型と \(V\) 通過型の節の種類と相対的な順序を決めましょう。これは \(C(i, j)\) 通り存在します。
• 次に、\(S \rightarrow T \rightarrow S\) と \(S \rightarrow V \rightarrow S\) の二種類の回帰型の節を挿入しましょう。この方法は \(C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2})\) 通り存在します。
• 次に、残り二種類の回帰型の節を挿入しましょう。この方法は \(C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})\) 通り存在します。

よって、答えは

\(\sum_{i,j} C(i, j) C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2}) C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})\).

であり、これは

\((\frac{a+d}{2})! (\frac{b+c}{2}-1)! \sum_{i,j} \frac{(i+j)!}{((i+j)/2)!((i+j)/2+1)!} \cdot \frac{1}{i!((a-i)/2)!((b-i)/2)!} \cdot \frac{1}{j!((c-j)/2)!((d-j)/2)!}\)

に等しく、FFT で高速に計算できます。