Think you can solve this?

I will try to use functions to prove this.

A bijective is defined as a function which is both one-one and onto(surjective).

In a bijective, number of elements in domain = number of elements of co-domain = (n) and range is equal to co-domain.

In a bijective, No. of one-one functions is equal to number of onto functions.

No.of. onto functions = $\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^m$ .

Here, m = n.

So, $\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n$ =no.of.one-one functions from n to n = n!.

Also, I think the power of -1 should be k not n.

Please correct me if I am wrong.

Suppose that we have $n$ distinct stones and $n$ distinct colors. We will calculate the number of ways to paint our stones such that each color is used. Obviously, this number is $n!$ . But, from PIE and complementary counting (we consider the cases where we don't use a finite number of colors), the number of ways is also the expression in the hypothesis. Thus, since they count the same quantity, the expressions must be equal. Hence, the answer is $n!$ .

I will use inductions to prove this.

Lemma 1: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)=0$ for all $n \ge 2$

Proof:

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)=n\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}-\sum_{k=1}^{n}(-1)^{k}\binom{n}{k}k$

Since $\binom{n}{k}k=\binom{n-1}{k-1}n$ and $0=(1-1)^n=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}$ , we have

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)=-n\sum_{k=1}^{n}(-1)^{k}\binom{n-1}{k-1}=n\sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}=n(1-1)^{n-1}=0$

The proof is done.

Lemma 2: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m} = 0$ for all $n \ge m+1$

Proof: (Induction)

By Lemma 1 , Lemma 2 holds when m = 1. Suppose $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m} = 0$ holds for $n\ge m+1$ , then for $n\ge m+2$ ,

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m+1}=n\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m}-\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}k(n-k)^{m}$

The first term on the RHS equals 0 by our assumption since $n\ge m+2\ge m+1$ , and the second term equals $-n\sum_{k=1}^{n}(-1)^{k}\binom{n-1}{k-1}(n-k)^{m}=n\sum_{k=1}^{n}(-1)^{k-1}\binom{n-1}{k-1}(n-k)^{m}=n\sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}(n-1-i)^{m}$ . This term equals 0 by our assumption since $n-1\ge m+1$ . So

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m+1}=0$ for all $n\ge m+2$

The proof is done.

Corollary: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{n-1} = 0$

Proof: This is a special case of Lemma 2 when m=n-1

The proof is done.

Theorem: $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{n} = n!$

Proof: The equation holds when n=1. Suppose $\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}(n-k)^{m} = m!$ holds when $m\le n$ , where $n\ge 1$ , then

$\sum_{k=0}^{m+1}(-1)^{k}\binom{m+1}{k}(m+1-k)^{m+1}=(m+1)\sum_{k=0}^{m+1}(-1)^{k}\binom{m+1}{k}(m+1-k)^{m}-\sum_{k=0}^{m+1}(-1)^{k}\binom{m+1}{k}k(m+1-k)^{m}$

The first term on the RHS equals 0 by the Corollary , and the second term

$-\sum_{k=0}^{m+1}(-1)^{k}\binom{m+1}{k}k(m+1-k)^{m}=(m+1)\sum_{k=1}^{m+1}(-1)^{k-1}\binom{m}{k-1}(m-(k-1))^{m}=(m+1)\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}(m-i)^{m} = (m+1)m! = (m+1)!$

So $\sum_{k=0}^{m+1}(-1)^{k}\binom{m+1}{k}(m+1-k)^{m+1} = (m+1)!$

The proof is done.

Ok so clearly you all guys are too intelligent to come up with such short and elegant solutions involving extreme logical thinking rather than pure algebraic maneuvers. But for a slow person like me who finds it toooo difficult to relate a summation to the number of ways of counting an event, I had to spend half an hour solving it explicitly by using formulas and identities: Write S= summation (-1)^(n-k).nCk.k^n (coz f(k) is replaced by f(a+b-k)) Now simply write k^n= k(k-1)...(k-(n-1))+ak(k-1)...(k-(n-2))+bk(k-1)...(k-(n-3))+.........+hk, where a, b,.....,h are undetermined coefficients. Using r.nCr= n.(n-1)C(r-1) repeatedly we will see that all these sums vanish except for the first term k(k-1)....(k-(n-1)).(-1)^(n-k).nCk. So we simply take its sum which is precisely it's value at n, i.e., n!

The result is trivial if you know the Stirling number of the second kind: $S(m, n) = \frac{1}{n!} \sum_{k=0}^n (-1)^k {n \choose k} (n-k)^m.$ Let $m = n$ and we get $S(n,n) = 1$ .

Here are the details for Nelson's solution (same as Alan's solution). I am writing it here, rather than as a reply, because of the latex support.

Let $A,B$ be finite sets.

For a subset $B'\subset B$ let $E(B')$ be the set of functions $A\rightarrow (B\setminus B')$ and for $b\in B$ let's write $E(b)$ instead of $E(\{b\})$ for short. Clearly $E(B') = \cap_{b \in B'} E(b)$ and $|E(B')| = (|B| - |B'|) ^{|A|}$

Clearly, $\cup_{b \in B'} E(b)$ is the set of all functions which are not onto, and therefore by PIE : $|\text{onto functions} | = \sum_{B'\subset B} (-1)^{|B'|} |E(B')| = \sum_{k=0}^{|B|} (-1)^k \cdot {|B|\choose k} \cdot (|B|-k)^{|A|}$ Taking $|A| = |B| = n$ the identity follows (because there are $n!$ onto functions in this case).

It also follows that $m < n \ \Longrightarrow \sum_{k=0}^{n} (-1)^k \cdot {n\choose k} \cdot (n-k)^{m} =0$

My solution is similar to Nelson's solution. I want to know if anyone has proved this equation using any other method. please do post if you have proved it by some other method!