Saturday, December 30, 2017

Summation of series involving binomial coefficients



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...