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.
Answer
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.
No comments:
Post a Comment