Let $$c_n=n!\sum\limits_{k=0}^n (-1)^k \frac{1}{k!}$$ be the number of derangements of $n$ elements. The following combinatorial identity is coming up in my research:
$$\sum\limits_{j=1}^{n-2}c_{n-j}{n-2\choose j-1}=(n-2)!(n-2)$$
Is there a known reference or proof for this identity? Simulations do support this.
I think this identity is true. It's quite similar to this. I'll give a combinatorial argument.
Let's try and count the number of permutations of $\{1, \dotsc, n - 1\}$ that do not fix $1$.
One way to count is to note that the number of permutations fixing $1$ is just the number of permutations of $\{2, \dotsc, n - 1\}$, so the answer is $(n - 1)! - (n - 2)! = (n - 2)!(n - 2)$. (Or you can argue that there are $n - 2$ choices for where to send $1$, then $n - 2$ choices for where to send $2$, then $n - 3$ choices for where to send $3$...)
Another way to count is more complicated: for each $1 \le j \le n - 2$, choose $j - 1$ elements of $\{2, \dotsc, n - 1\}$ to keep fixed (note a permutation cannot fix all but one element), and then choose a derangement of the remaining $n - j$ elements of $\{1, \dotsc, n - 1\}$. This counts each of the permutations we're interested in exactly once, so it follows that \begin{equation*} \sum_{j = 1}^{n - 2} c_{n - j} \binom{n - 2}{j - 1} = (n - 2)!(n - 2). \end{equation*}
I can't find any references - since it's quite straightforward to prove, I don't think there will necessarily be a really good reference, nor does it really require one.
