一个三重求和下的组合数问题

求下面式子的值：

Sm=∑w=1mw!∑k=0w∑j=0k(−1)k+j(k+j)!(kj)(mk+j)S_m=\sum_{w=1}^mw!\sum_{k=0}^w\sum_{j=0}^k(-1)^{k+j}(k+j)!\binom kj\binom m{k+j}

Mathematica给出的不明所以的做法：

构造整式递推数列 f(n)f(n)

{f(0)=0f(1)=1f(2)=1−(2−m)mf(n+3)=−(6n3−9n2m+19n2+5nm2−20nm+17n−m3+6m2−9m+4)f(n+1)+(−8n3+12n2m−24n2−6nm2+26nm−22n+m3−7m2+13m−5)f(n+2)+(n+1)(n−m)(2n−m+3)f(n)(2n−m+1)\begin{cases}f(0)=0\\f(1)=1\\f(2)=1-(2-m) m\\f(n+3)=-\frac{\left(6 n^3-9 n^2 m+19 n^2+5 n m^2-20 n m+17 n-m^3+6 m^2-9 m+4\right) f(n+1)+\left(-8 n^3+12 n^2 m-24 n^2-6 n m^2+26 n m-22 n+m^3-7 m^2+13 m-5\right) f(n+2)+(n+1) (n-m) (2 n-m+3) f(n)}{(2 n-m+1)}\end{cases}

可以证明

Sm=∑w=1mw!f(w+1)S_m=\sum_{w=1}^mw!f(w+1)

逐项递推求值，可做到时间复杂度 O(m)\mathcal O(m)。用整式递推甚至还可以做到 O(m)\mathcal O(\sqrt m)