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?
We can give a combinatorial proof. Both sides are answers to the following question:
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.