help calculating $\sum_{k=0}^n k!{n \choose k} ^2= \text{?}$ I am trying to find the number of relations on $[n] = \{1,\ldots,n\}$ s.t. for all $x,y,z\in R.xRz \wedge yRz\to x=y$. One idea I had was choosing $k$ elements from $n$ then choosing another $k$ elements from $n,$ there are $k!$ bijections between these two sets so we just have to sum over $k$ and here I got stuck, tried finding another approach but came up with nothing.
 A: Let $R$ be such a relation. For each $z\in[n]$ there is at most one $x\in[n]$ such that $x\mathrel{R}z$. The relation $R$ therefore defines a function
$$f_R:[n]\to[n+1]:z\mapsto\begin{cases}
x,&\text{if }R^{-1}[\{z\}]=\{x\}\\
n+1,&\text{if }R^{-1}[\{z\}=\varnothing\,.
\end{cases}$$
In other words, $f_R(z)$ is the unique $x\in[n]$ such that $x\mathrel{R}z$ if there is one and is $n+1$ if no such $x\in[n]$ exists.
Conversely, if $g$ is any function from $[n]$ to $[n+1]$, the relation
$$R_g=\{\langle f(k),k\rangle:k\in[n]\}\cap\big([n]\times[n]\big)$$
has the desired property, and $f_{R_g}=g$. Thus, the map $R\mapsto f_R$ is a bijection from the set of such relations to the set of functions from $[n]$ to $[n+1]$. There are $(n+1)^n$ functions from $[n]$ to $[n+1]$ and therefore $(n+1)^n$ such relations.
A: Your approach is missing relations as commented above, you are considering just injective partial functions. To complete your argument You can go as follows: You pick a set of $[n]$ for the domain(say of size $k$) of the relation and you choose a different set of the codomain (say one of size $\ell$). Then you partition the codomain(into $k$ non empty blocks) and assign each block to an element in the domain (so you permute the blocks in $k!$ ways). I get
$$\sum _{k,\ell}\binom{n}{\ell}\binom{n}{k}{\ell \brace k}k!=\sum _{\ell= 0}^n\binom{n}{\ell}\sum _{k=0}^n\binom{n}{k}{\ell \brace k}k!=\sum _{\ell= 0}^n\binom{n}{\ell}n^{\ell}=(n+1)^n.$$
Which makes sense, your relation is the functional relation for the right coordinate and you are just adding a dummy image to see when is the element not in the domain.
A: Every relationship from $[n]$ to $[n]$ is just a subset of $[n]\times [n]$, so consider the $n\times n$ grid, what you have calculated is placing $k$ non-threating rooks on the grid. Your answer is equal to the sum of coefficients of the "rook polynomial" and does not have a closed form.
However, what this problem is asking is to place $k$ rooks on the $n\times n$ grid while they threat each other only on one axis, for example just vertically.
To count the answer over all $k$s, for each column of the grid, one can pick the position of the corresponding rook with a number between $0$ to $n$, where $0$ is leaving the rook outside of the grid.
This leads to $(n+1)^n$ possible outcomes.
A: The following function is used in statistical thermodynamics.
$$f(x)=\sum_{k=0}^n {n \choose k} ^2\,k!\,x^k= (-x)^n U\left(-n,1,-\frac{1}{x}\right)$$ where appears the Tricomi confluent hypergeometric function.
So, your case corresponds to $f(1)$ and the values are reported as sequence $A002720$ in $OEIS$. Accoring to $OEIS$, $a_n= n!\, L_n(-1)$ where appear   Laguerre polynomials.
