Prove that

$$\sum_{k=0}^{n-2}(-1)^k \binom {n-2}{k} (n-2-k)^n=(n-2)!\left(\binom{n}{3}+3\binom {n}{4}\right)\;.$$

I was trying the use the inclusion-exclusion principle to prove this equation but I couldn't figure it out.


closed as off-topic by Carl Mummert, Bruno Joyal, Branimir Ćaćić, ncmathsadist, user61527 Dec 2 '13 at 1:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Bruno Joyal, Branimir Ćaćić, ncmathsadist, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This question lacks key context that would help others answer it. Why do you suspect the equation is true in the first place? Did you encounter it in a class or textbook, and if so, which one? Did you have a hint to use inclusion/exclusion? $\endgroup$ – Carl Mummert Dec 2 '13 at 0:28

For a $k$-subset $X$ of $\{1,2,\ldots,n-2\}$, there are $(n-2-k)^n$ functions

$$f : \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n-2\}$$

that have range contained in $\{1,2,\ldots,n-2\} \backslash X$. Therefore the left-hand side is the inclusion-exclusion count of the number of surjective functions from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n-2\}$.

If $f$ is such a function then either there exist three elements of $\{1,2,\ldots,n\}$ with the same image, or there are two $2$-subsets $\{i,j\}$, $\{k,\ell\}$ such that $f(i)=f(j)\not=f(k)=f(\ell)$. There are $(n-2)!\binom{n}{3}$ functions of the first type and $$(n-2)!\frac{1}{2}\binom{n}{2,2,n-4} = (n-2)!\times 3\binom{n}{4}$$ functions of the second type.


Not the answer you're looking for? Browse other questions tagged or ask your own question.