Closed form for product of Stirling numbers of the second kind

Question

What does the following expression evaluate to:

\begin{equation} \sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \end{equation}

We know that $k! \begin{Bmatrix} n \\ k \end{Bmatrix} = n![x^n]:(e^x-1)^k$, where $[x^k]:f(x)$ represents the coefficient of $x^k$ in the power series for $f(x)$. I was wondering if squaring $\left(\text{i.e., } k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix}\right)$ takes us to a different power series or just to a different coefficient in the same power series? I am looking for some clean closed form. A related expression:

\begin{equation} \sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \end{equation}

is proven to be equal to $n^n$ in this answer https://math.stackexchange.com/q/3076350.

Answer 1

We have \begin{split} \sum_{k=0}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} &= n!^2[x^ny^n] \sum_{k=0}^n \binom{n}{k} ((e^x-1)(e^y-1))^k \\ &=n!^2[x^ny^n] (2-e^x-e^y+e^{x+y})^n. \end{split} Here we can use Lagrange inversion (over $x$) to obtain $$=n!^2[y^nz^n]\ 1 - t(y,z)W'(t(y,z)) = n!^2[y^nz^n]\ \sum_{k\geq 0} \frac{(-k)^k}{k!} t(y,z)^k$$ where $t(y,z):=z(1-e^y)e^{z(2-e^y)}$ and $W(\cdot)$ is Lambert W function. In general, extracting the diagonal (in a closed form) of a bivariate generating function is hard, and this is the case here.

Nevertheless, let's play a bit with the last expression. Extracting the coefficients first of $z^n$ and then of $y^n$ we get \begin{split} & n!^2[y^n]\ \sum_{k=0}^n \frac{k^n}{k!} (e^y-1)^k \frac{(2-e^y)^{n-k}}{(n-k)!} \\ =& n!^2[y^n]\ \sum_{k=0}^n \frac{k^n}{k!(n-k)!} \sum_{m=0}^{n-k} \binom{n-k}{m} (-1)^m (e^y-1)^{m+k} \\ =& \sum_{k=0}^n k^n \sum_{m=0}^{n-k} \frac{n!(m+k)!}{k!m!(n-k-m)!} (-1)^m \left\{ n\atop m+k\right\}. \end{split} Hence, we got another expression (not necessarily simpler) for the same quantity.

Answer 2

For that matter, another alternative expression, obtained by substituting $\let\le\leqslant$ $ k!\left\{n\atop k\right\}=\sum_{i=0}^k(-1)^{k-i}\binom kii^n: $ $$ \sum_{k=0}^n\binom nk\left(k!\left\{n\atop k\right\}\right)^2=\sum_{1\le i,j\le n}(-1)^{i+j}\sum_{k=\max(i,j)}^n\binom nk\binom ki\binom kj(ij)^n. $$ According to Mathematica, for $j\le i$ $$ \sum_{k=i}^n\binom nk\binom ki\binom kj=\frac{n!}{j!(i-j)!(n-i)!}{}_2F_1(i+1,i-n;i-j+1;-1), $$ so that we obtain \begin{multline*} \sum_{m\le n^2}\left(\sum_{m=d^2,d\le n}\binom nd{}_2F_1(d+1,d-n;1;-1)\right.\\\left.+2\left(\sum_{d|m,\sqrt m<d\le n}(-1)^{d+\frac md}\frac{n!}{\frac md!(d-\frac md)!(n-d)!}{}_2F_1(d+1,d-n;d-\frac md+1;-1)\right)\right)m^n. \end{multline*}

Resulting expressions for small $n$: $$ \begin{array}{rrrrrrrrrrrrrrr} 1=&\!\!\!\!\!1^1\\ 6=&\!\!\!\!\!6\cdot1^2&\!\!\!\!\!-4\cdot2^2&\!\!\!\!\!&\!\!\!\!\!+4^2\\ 147=&\!\!\!\!\!24\cdot1^3&\!\!\!\!\!-30\cdot2^3&\!\!\!\!\!+6\cdot3^3&\!\!\!\!\!+12\cdot4^3&\!\!\!\!\!-6\cdot6^3&\!\!\!\!\!&\!\!\!\!\!+9^3\\ 6940=&\!\!\!\!\!80\cdot1^4&\!\!\!\!\!-144\cdot2^4&\!\!\!\!\!+56\cdot3^4&\!\!\!\!\!+70\cdot4^4&\!\!\!\!\!-72\cdot6^4&\!\!\!\!\!+12\cdot8^4&\!\!\!\!\!+20\cdot9^4&\!\!\!\!\!-8\cdot12^4+16^4 \end{array} $$ Empirically, this seems to be \begin{multline*} \binom n12^{n-1}2(n+1)1^n-\binom n22^{n-2}(n+2)2^n+\binom n32^{n-3}(n+3)3^n\\ -\binom n42^{n-4}\frac{n^3-7n^2-32n+36}{(n-2)(n-3)}4^n+\binom n52^{n-5}(n+5)5^n\\-\binom n62^{n-6}\frac{n^4-6n^3+215n^2+1422n-360}{(n-3)(n-4)(n-5)}6^n+\binom n72^{n-7}(n+7)7^n+... \end{multline*}

However I admit this might be harder to further evaluate than the OP expression...