Counting endofunctions by inclusion–exclusion While leafing through the OEIS, I noticed the following conjecture (from  Werner Schulte,
OEIS A000312 ):
For integer $n \ge 0$
$$  \sum_{k=0}^n  (-1)^{n - k} { n \brack k }{n+k \brace k} =  n^n . $$
Here ${ n \brack k }$ denotes the unsigned Stirling cycle numbers and $\left\{ {n} \atop  k\right\}$ the Stirling set numbers.
This led me to wonder whether $T(n,k) := { n \brack k } {n+k \brace k}$ is the number of simple combinatorial or set theoretical objects.
Can anyone describe such objects and derive the conjecture from them?
 A: We can give a combinatorial proof. Both sides are answers to the following question:

There are $n$ adults and $n$ children. How many ways are there to divide these $2n$ people into $n$ unlabeled groups so that every group has an adult?

Obviously, the answer is $n^n$, since you just need to specify, for each child, which adult they go with.
To explain the other side of the equation, let $P$ denote the set of all ways to partition the $2n$ children and adults into $n$ unlabeled groups, without requiring each group to have an adult, so $|P|={2n \brace n}$. Let $S$ be the set of permutations of the adults. Note that $S$ acts on $P$; given a partition $\pi$ and permutation $\sigma$, we define $\sigma\circ \pi$ to be the partition where $\pi$ is modified by moving adult number $i$ to the current part containing adult number $\sigma(i)$, for each $i\in \{1,\dots,n\}$. Finally, let $\Omega$ be the set of all ways a partition in $P$ can be unchanged by a permutation in $S$:
$$
\Omega=\{(\pi,\sigma)\mid \pi\in P, \sigma\in S, \sigma \circ \pi = \pi\}
$$
We have concocted this funny set $\Omega$ to explain the summation $\sum_{k=0}^n (-1)^{n-k}{n \brack k}{n+k\brace n}$. Specifically, we can show that
$$
\sum_{(\pi, \sigma)\in \Omega}(-1)^{\text{sign}(\sigma)}=\sum_{k=0}^n(-1)^{n-k}{n \brack k}{n+k \brace n}\tag1
$$
That is, the LHS just enumerates $\Omega$, except where permutations are counted by their parity. Indeed, for any $k$, there are ${n\brack k}$ ways to choose a permutation $\sigma$ with $k$ cycles, each of which comes with a sign of $(-1)^{n-k}$. Then, in order to choose a partition $\pi$ for which $\sigma \circ \pi=\pi$, for each cycle of $\pi$, all of the adults in that cycle need to be placed in the same part, so they act like a unit. There are then only $n+k$ units to distribute, hence the ${n + k \brace n}$.
All that remains is to establish how $\sum_{(\pi,\sigma)\in \Omega}(-1)^{\text{sign}(\sigma)}$ relates to counting partitions where every part has an adult.
This follows from the following sign-reversing involution defined on $\Omega$. Define
\begin{align}
f:\,&\Omega\to \Omega\\
&(\pi,\sigma)\mapsto (\pi, \tau_\pi \circ \sigma),
\end{align}
where $\tau_\pi$ is defined to be the transposition in $S$ which swaps parents numbered $i$ and $j$, where $(i,j)$ is the lexicographically earliest pair of parents which are in the same part. If no such pair exists, then we leave $f$ undefined.
You can show that $f(f(\omega))=\omega$ for all $\omega\in \Omega$ such that $f(\omega)$ is defined. This is because swapping $i$ and $j$ does not affect the set of parents which are in the same part, so applying $f$ again swaps the same $i$ and $j$. Therefore, $f$ is an order $2$ permutation on its domains, so it defines a partition of its domain into pairs. In each pair $\{\omega,f(\omega)\}$, the two elements have opposite signs, so they cancel each other out in $\sum_{(\pi,\sigma)\in \Omega} (-1)^{\text{sign}(\sigma)}$. The only thing that remains are the ordered pairs $(\pi,\sigma)$ for which $f$ is undefined. But these are precisely the partitions $\pi$ where all parents are in different parts and where $\sigma$ is the identity permutation. Therefore,
$$
\sum_{(\pi,\sigma)\in \Omega} (-1)^{\text{sign}(\sigma)}=|\{\pi\in P\mid \text{every part of $\pi$ has an adult}\}|=n^n\tag2 
$$
Combining $(1)$ and $(2)$, the conjectured equation is proven.
A: I'm not sure an algebraic proof is acceptable to OP, will post and
wait for feedback. We seek to show that
$$\sum_{k=0}^n (-1)^{n-k} {n\brack k} {n+k\brace n} = n^n.$$
We get from the standard Stirling set number EGF
$$\sum_{k=0}^n (-1)^{n-k} {n\brack k}
\frac{(n+k)!}{n!} [z^{n+k}] (\exp(z)-1)^n
\\ = \sum_{k=0}^n (-1)^{n-k} {n\brack k}
\frac{(n+k)!}{n!} [z^{n+k}]
\sum_{q=0}^n {n\choose q} (-1)^{n-q} \exp(qz)
\\ = \sum_{k=0}^n (-1)^{n-k} {n\brack k}
\frac{(n+k)!}{n!}
\sum_{q=0}^n {n\choose q} (-1)^{n-q} \frac{q^{n+k}}{(n+k)!}
\\ = \frac{1}{n!}
\sum_{q=0}^n {n\choose q} (-1)^{n-q} q^n
\sum_{k=0}^n (-1)^{n-k} {n\brack k} q^k.$$
The signed Stirling cycle OGF is $n! \times {z\choose n}$ so we find
$$\sum_{q=0}^n {n\choose q} (-1)^{n-q} q^n {q\choose n}.$$
The only term that contributes here is $q=n$ and we get
$${n\choose n} (-1)^{n-n} n^n {n\choose n} = n^n$$
which is the claim.
