Evaluate weighted stirling number sum - $\sum_{i=0}^n k*c(n,k)$

Question

How to evaluate
$$\sum_{k=0}^n k*c(n,k)$$
Where $c(n,k)=|s(n,k)|$ is the stirling number of the first kind without a sign.

Answer 1

Differentiation of the falling factorial is definitely the way to go, as @Phicar noted. Given that we know $$x^{\underline{n}}=\sum _{k=0}^n S_n^k\,x^k$$ All we have to do is let $x \to -x$, multiply by $(-1)^n$, and differentiate both sides and to get $$(-1)^n(-x)^{\underline{n}}(H_{-n-x}-H_{-x})=\sum _{k=0}^n k\,x^{k-1}S_n^k(-1)^{n-k}=\sum _{k=0}^n k\,x^{k-1}c(n,k)$$ Now just let $x=1$. The LHS will simplify significantly when you do.

Answer 2

It turns out that $$ \sum_{k=1}^n kc(n,k)=c(n+1,2), $$ which I shall prove bijectively. Both sides have a natual combinatorial interpretation:

• $\sum_{k=1}^nkc(n,k)$ is equal to the number of ways to choose a permutation on $\{1,\dots,n\}$, and then to single out one of the cycles as "special".

• $c(n+1,2)$ enumerates permutations of $\{0,1,\dots,n\}$ with exactly two cycles.

I will give a bijection between these two sets, which completes the proof.

Given a permutation of $\{0,1,\dots,n\}$ with exactly two cycles, we need to define a permutation $\pi$ of $\{1,\dots,n\}$, such that one cycle of $\pi$ is singled out as special. Call the two cycles $\sigma$ and $\tau$, where $\sigma$ is the cycle containing $0$. We will let $\tau$ be the "special" cycle. All that remains is to define the action of $\pi$ on the nonzero elements of $\sigma$. We can write $\sigma$ with the $0$ first, so in the form $$ \sigma=(0,\;\sigma_1,\;\sigma_2,\;\dots\;\sigma_k), $$ For each $i\in \{1,\dots,k\}$, let $\sigma_i'$ be the $i^\text{th}$ smallest element of $\{\sigma_1,\dots,\sigma_k\}$. We then define the action of $\pi$ on the nonzero elements of $\sigma$ by defining $$ \pi(\sigma_i')=\sigma_i,\qquad \text{for each }i\in \{1,\dots,k\} $$

Answer 3

We seek to verify that

$$\sum_{k=0}^n k {n\brack k} = {n+1\brack 2}.$$

This is

$$n! [z^n] \sum_{k=1}^n k \frac{1}{k!} \left(\log\frac{1}{1-z}\right)^k.$$

Here we can extend to infinity due to the coefficient extractor and the fact that $\log\frac{1}{1-z} = z +\cdots$:

$$n! [z^n] \log\frac{1}{1-z} \sum_{k\ge 1} \frac{1}{(k-1)!} \left(\log\frac{1}{1-z}\right)^{k-1} \\ = n! [z^n] \log\frac{1}{1-z} \exp\log\frac{1}{1-z} = n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! \times H_n.$$

On the other hand we have

$${n+1\brack 2} = (n+1)! [z^{n+1}] \frac{1}{2} \left(\log\frac{1}{1-z}\right)^2 \\ = (n+1)! \frac{1}{2} \sum_{q=1}^n \frac{1}{q} \frac{1}{n+1-q} \\ = n! \frac{1}{2} \sum_{q=1}^n \left(\frac{1}{q} + \frac{1}{n+1-q}\right) = n! \times H_n$$

and we have the claim. We can prove that $\exp\log\frac{1}{1-z} = \frac{1}{1-z}$ using the combinatorial class $\mathcal{P}$ of permutations which are sets of cycles:

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

as presented in Analytic Combinatorics by Flajolet amd Sedgewick.