Thursday, June 6, 2019

summation - Equality of the sums $sumlimits_{v=0}^k frac{k^v}{v!}$ and $sumlimits_{v=0}^k frac{v^v (k-v)^{k-v}}{v!(k-v)!}$



How can one proof the equality
$$\sum\limits_{v=0}^k \frac{k^v}{v!}=\sum\limits_{v=0}^k \frac{v^v (k-v)^{k-v}}{v!(k-v)!}$$

for $k\in\mathbb{N}_0$?



Induction and generating functions don't seem to be useful.



The generation function of the right sum is simply $f^2(x)$ with $\displaystyle f(x):=\sum\limits_{k=0}^\infty \frac{(xk)^k}{k!}$



but for the left sum I still don't know.



It is $\displaystyle f(x)=\frac{1}{1-\ln g(x)}$ with $\ln g(x)=xg(x)$ for $\displaystyle |x|<\frac{1}{e}$.


Answer




Recall the combinatorial class of labeled trees which is



$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z}\times \textsc{SET}(\mathcal{T})$$



which immediately produces the functional equation



$$T(z) = z \exp T(z)
\quad\text{or}\quad
z = T(z) \exp(-T(z)).$$




By Cayley's theorem we have



$$T(z) = \sum_{q\ge 1} q^{q-1} \frac{z^q}{q!}.$$



This yields



$$T'(z) = \sum_{q\ge 1} q^{q-1} \frac{z^{q-1}}{(q-1)!}
= \frac{1}{z} \sum_{q\ge 1} q^{q-1} \frac{z^{q}}{(q-1)!}
= \frac{1}{z} \sum_{q\ge 1} q^{q} \frac{z^{q}}{q!}.$$




The functional equation yields



$$T'(z) = \exp T(z) + z \exp T(z) T'(z)
= \frac{1}{z} T(z) + T(z) T'(z)$$



which in turn yields



$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}$$




so that



$$\sum_{q\ge 1} q^{q} \frac{z^{q}}{q!}
= \frac{T(z)}{1-T(z)}.$$



Now we are trying to show that



$$\sum_{v=0}^k \frac{v^v (k-v)^{k-v}}{v! (k-v)!}
= \sum_{v=0}^k \frac{k^v}{v!}.$$




Multiply by $k!$ to get



$$\sum_{v=0}^k {k\choose v} v^v (k-v)^{k-v}
= k! \sum_{v=0}^k \frac{k^v}{v!}.$$



Start by evaluating the LHS.

Observe that when we multiply two
exponential generating functions of the sequences $\{a_n\}$ and
$\{b_n\}$ we get that



$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!}

\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$



i.e. the product of the two generating functions is the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$




In the present case we have
$$A(z) = B(z) = 1 + \frac{T(z)}{1-T(z)}
= \frac{1}{1-T(z)} $$
by inspection.




We added the constant term to account for the fact that $v^v=1$ when
$v=0$ in the convolution. We thus have



$$\sum_{v=0}^k {k\choose v} v^v (k-v)^{k-v}

= k! [z^k] \frac{1}{(1-T(z))^2}.$$



To compute this introduce



$$\frac{k!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{(1-T(z))^2} \; dz$$



Using the functional equation we put $z=w\exp(-w)$ so that $dz =
(\exp(-w)-w\exp(-w)) \; dw$
and obtain




$$\frac{k!}{2\pi i}
\int_{|w|=\gamma}
\frac{\exp((k+1)w)}{w^{k+1}} \frac{1}{(1-w)^2}
(\exp(-w)-w\exp(-w)) \; dw
\\ = \frac{k!}{2\pi i}
\int_{|w|=\gamma}
\frac{\exp(kw)}{w^{k+1}} \frac{1}{1-w} \; dw$$



Extracting the coefficient we get




$$k! \sum_{v=0}^k [w^v] \exp(kw) [w^{k-v}] \frac{1}{1-w}
= k! \sum_{v=0}^k \frac{k^v}{v!}$$



as claimed.


Remark. This all looks very familiar but I am unable to locate the
duplicate among my papers at this time.


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...