2
$\begingroup$

I need to compute $S_{n} = \sum_{k=0}^{n} \binom{n}{k}(-1)^k(n-k)^n$. $S_{2} = 2, S_{3} = 6,S_{4}=24$ therefore i think answer is $S_{n} = n!$. And i have got $S_{n}=(\Delta^n(n-x)^n)(0)$. But it gives no benefit to me..

$\endgroup$
  • $\begingroup$ Have you tried induction? $\endgroup$ – MarkG Feb 23 '15 at 13:46
  • $\begingroup$ Yes, but with the same result(fail). $\endgroup$ – qwenty Feb 23 '15 at 13:47
  • $\begingroup$ The following MSE link may prove useful reading. $\endgroup$ – Marko Riedel Feb 23 '15 at 20:51
3
$\begingroup$

If you apply $n$ times the forward (backward) difference operator to a monic polynomial in $x$ having degree $n$ you get a constant that just depends on the degree of the polynomial. For a combinatorial interpretation, $n!$ is the number of bijective functions from $A=\{1,\ldots,n\}$ to $B=\{1,\ldots, n\}$. How many functions $f:A\to B$ do we have such that $|f(A)|=n-k$? Obviously $\binom{n}{k}(n-k)^n$. Conclude by inclusion-exclusion.

$\endgroup$
2
$\begingroup$

Hint

It's precisely the cardinality of the set $$\left\{f:\{1,2,...,n\}\to \{1,2,...,n\}\mid f\ \text{ is onto (or surjective)}\right\}$$

Moreover, you know that a function $f:\{1,...,n\}\to\{1,...,n\}$ is onto if and only if is injective and thus bijective. I let you continue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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