公式解説では DP の連結成分内に順序があると定義していましたが、順序がないと考えても解けます。
この場合において、遷移にかかる係数は連結成分が \(j\) から \(j+1,j,j-1\) になる際にそれぞれ \(1,2j,j \left( j-1 \right)\) です。