<s>[INST] Prove that $\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$ I figure out these thing when "playing" with numbers:
$$3^2-2.2^2+1^2=2=2!$$
$$4^3-3.3^3+3.2^3-1^3=6=3!$$
$$5^4-4.4^4+6.3^4-4.2^4+1^4=24=4!$$
So I go to the conjecture that:
$$\binom{n}{n}(n+1)^n-\binom{n}{n-1}n^n+\binom{n}{n-2}(n-1)^n-...=n!$$
or
$$\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$$
Now, how can I prove this conjecture? I've tried a lot, but still couldn't have any idea.
 [/INST] Here is a combinatorial proof: consider the set $F$ of functions $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n, n + 1 \}$, and for $k = 1, \ldots, n$, let $S_k$ be the set of such functions such that $k$ is not in the range.  Then, by inclusion-exclusion:
$$\left|F \setminus \bigcup_{k=1}^n S_k \right| = |F| - \sum_{1 \le i \le n} |S_i| + \sum_{1 \le i < j \le n} |S_i \cap S_j| - \sum_{1 \le i < j < k \le n} |S_i \cap S_j \cap S_k| + \cdots + (-1)^n |S_1 \cap \cdots \cap S_n|.$$
Now, $|F| = (n+1)^n$; for each $i$, $|S_i| = n^n$, so the second term is $-\binom{n}{1} n^n$; for each $i < j$, $|S_i \cap S_j| = (n-1)^n$, so the third term is $\binom{n}{2} (n-1)^n$; and so on.  Therefore, the sum on the right hand side is equal to the left hand side of your equation (using that $\binom{n}{n-x} = \binom{n}{x}$).  On the other hand, $F \setminus \bigcup_{k=1}^n S_k$ is exactly the set of functions such that each of $1, 2, \ldots, n$ is in the range, which is precisely the set of permutations of $\{ 1, 2, \ldots, n \}$; therefore, the left hand side is equal to $n!$.
In fact, if we let $F$ be the set of functions $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n + r \}$ instead, this argument easily generalizes to show that for $n$ a positive integer and $r$ a nonnegative integer:
$$\sum_{x=0}^n (-1)^k \binom{n}{x} (n+r-x)^n = n!.$$
</s>