3
$\begingroup$

Find the following sum:

$$\sum _{r=0}^{15} {^{15}C_{r}} \hspace{2 mm} (15-r)^{15} \hspace{2 mm} (-1)^r$$

Now here the issue I am facing is that exponent of $(15-r)$ is fixed but the base is varying so how do we deal with that.I also tried writing series in reverse order but add up two equations but that also didn't help. Could someone help me with this.

$\endgroup$
  • 1
    $\begingroup$ I suppose ${^{15}C_{r}}$ is the binomial coefficient $\binom{15}r$? $\endgroup$ – Fimpellizieri May 19 '17 at 17:34
4
$\begingroup$

Let $A=\{1,\ldots,15\}$. I claim that the sum $$\sum_{r=0}^\infty(-1)^r\binom{15}r(15-r)^{15}$$ is the number of surjective functions from $A$ to $A$ (so $15!$). Let $F$ be the set of all functions from $A$ to $A$. Then $|F|=15^{15}$, the $r=0$ term of the sum. Let $F_j$ be the set of functions in $F$ with $f(k)\ne j$ for all $k$. The surjective functions in $F$ are those in $$F-(F_1\cup F_2\cup\cdots\cup F_{15}).$$ Use inclusion-exclusion to count this set. There are $\binom{15}r$ $r$-fold intersections of the $F_j$, and each of these has $(15-r)^{15}$ elements.

$\endgroup$
  • $\begingroup$ Brilliant and very clear! +1 $\endgroup$ – Fimpellizieri May 19 '17 at 17:37

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.