3
$\begingroup$

The question is to calculate a following sum: \begin{equation} {\mathcal S}_p(n) :=\sum\limits_{1\le j_1 < j_2 < \dots <j_p \le n-1} \prod\limits_{q=1}^p \frac{1}{n-j_q} \end{equation} for $p=1,2,..$ and $n\ge 1$. From purely combinatorial reasoning we have: \begin{eqnarray} {\mathcal S}_1(n) &=& H_{n-1} \\ {\mathcal S}_2(n) &=& \frac{1}{2!} \left(H_{n-1}^2 - H^{(2)}_{n-1} \right) \\ {\mathcal S}_3(n) &=& \frac{1}{3!} \left(H_{n-1}^3 - 3 H_{n-1} H_{n-1}^{(2)} + 2 H_{n-1}^{(3)}\right) \\ {\mathcal S}_4(n) &=& \frac{1}{4!} \left(H^4_{n-1} - 6 H_{n-1}^2 H_{n-1}^{(2)} + 8 H_{n-1} H_{n-1}^{(3)} + 3 H_{n-1}^{(2)} H_{n-1}^{(2)} - 6 H_{n-1}^{(4)}\right) \\ {\mathcal S}_5(n) &=& \frac{1}{5!} \left(H_{n-1}^5 - 10 H_{n-1}^3 H_{n-1}^{(2)} + 20 H_{n-1}^2 H_{n-1}^{(3)} + 15 H_{n-1} ((H_{n-1}^{(2)})^2 - 2 H_{n-1}^{(4)}) - 20 H_{n-1}^{(2)} H_{n-1}^{(3)} + 24 H_{n-1}^{(5)}\right) \\ {\mathcal S}_6(n) &=& \frac{1}{6!} \left(H_{n-1}^6 - 15 H_{n-1}^4 H_{n-1}^{(2)} + 40 H_{n-1}^3 H_{n-1}^{(3)} + 45 H_{n-1}^2 ((H_{n-1}^{(2)})^2 - 2 H_{n-1}^{(4)}) - 24 H_{n-1} (5 H_{n-1}^{(2)} H_{n-1}^{(3)} - 6 H_{n-1}^{(5)}) + 5 (-3 (H_{n-1}^{(2)})^3 + 18 H_{n-1}^{(2)} H_{n-1}^{(4)} + 8 ((H_{n-1}^{(3)})^2 - 3 H_{n-1}^{(6)}) \right) \end{eqnarray} where $H_{n-1}^{(r)} := \sum\limits_{j=1}^{n-1} 1/j^r$ is the generalised Harmonic number.

Is it possible to find the result for generic $p\ge 1$?

$\endgroup$
  • 1
    $\begingroup$ No idea how to get a compact expression for $\mathcal{S}_p(n)$ in general. However, we have $$1 + \sum_{p=1}^{n-1} \mathcal{S}_p(n) z^p = \prod_{k=1}^{n-1}\left(1 + \frac{z}{n-k}\right) = \prod_{k=1}^{n-1}\left(1 + \frac{z}{k}\right) = \exp\left[\sum_{k=1}^{n-1}\log\left(1+\frac{z}{k}\right)\right] = \exp\left[\sum_{p=1}^\infty \frac{(-1)^{p-1}}{p} \left(\sum_{k=1}^{n-1}\frac{1}{k^p}\right)z^p\right] = \exp\left[\sum_{p=1}^\infty \frac{(-1)^{p-1} H_{n-1}^{(p)}}{p} z^p\right] $$ and you can expand the RHS as a formal power series in $z$ to obtain expression for other $\mathcal{S}_p(n)$. $\endgroup$ – achille hui Jan 17 '14 at 15:42
  • 1
    $\begingroup$ See the sequence A181897 in OEIS $\endgroup$ – Leox Jan 17 '14 at 16:23
1
$\begingroup$

Start with $$1 + \sum_{p=1}^{n-1} \mathcal{S}_p(n) z^p = \prod_{k=1}^{n-1}\left(1 + \frac{z}{n-k}\right) = \prod_{k=1}^{n-1}\left(1 + \frac{z}{k}\right) = \exp\left[\sum_{k=1}^{n-1}\log\left(1+\frac{z}{k}\right)\right] = \exp\left[\sum_{p=1}^\infty \frac{(-1)^{p-1}}{p} \left(\sum_{k=1}^{n-1}\frac{1}{k^p}\right)z^p\right] = \exp\left[\sum_{p=1}^\infty \frac{(-1)^{p-1} H_{n-1}^{(p)}}{p} z^p\right]$$ Taking logarithm and apply $z\frac{\partial}{\partial z}$ on both sides, we get

$$\sum_{p=1}^{n-1}p\mathcal{S}_p(n) z^p = \left(\sum_{p=1}^\infty (-1)^{p-1} H_{n-1}^{p} z^p\right) \left(1 + \sum_{p=1}^{n-1}\mathcal{S}_p(n) z^p\right) $$ Expanding both sides and compare coefficients of $z^p$, we obtain a chain of identities:

$$\begin{align} \mathcal{S}_1(n) &= H_{n-1}\\ 2\,\mathcal{S}_2(n) &= H_{n-1} \mathcal{S}_1(n) - H_{n-1}^{(2)}\\ 3\,\mathcal{S}_3(n) &= H_{n-1} \mathcal{S}_2(n) - H_{n-1}^{(2)}\mathcal{S}_1(n) + H_{n-1}^{(3)}\\ 4\,\mathcal{S}_4(n) &= H_{n-1} \mathcal{S}_3(n) - H_{n-1}^{(2)}\mathcal{S}_2(n) + H_{n-1}^{(3)}\mathcal{S}_1(n) - H_{n-1}^{(4)}\\ &\;\vdots\\ p\,\mathcal{S}_p(n) &= \left(\sum_{k=1}^{p-1}(-1)^{k-1} H_{n-1}^{(k)} \mathcal{S}_{p-k}(n)\right) + (-1)^{p-1} H_{n-1}^{(p)} \end{align}$$

This is the Newton's identities associated with the set of numbers $\;\displaystyle \frac{1}{n-j}\;$ for $1 \le j \le n-1$. One can use it to obtain the expression of $\mathcal{S}_p$ for higher $p$ recursively. Let $h_p = H_{n-1}^{(p)}$, following are some more $\mathcal{S}_p$ computed by this approach. $$\begin{array}{rcl} 6!\mathcal{S}_{6}(n) &=& -120{h}_{6}+144{h}_{1}{h}_{5}+90{h}_{2}{h}_{4}-90{h}_{1}^{2}{h}_{4}+40{h}_{3}^{2}-120{h}_{1}{h}_{2}{h}_{3}\\ &&+40{h}_{1}^{3}{h}_{3}-15{h}_{2}^{3}+45{h}_{1}^{2}{h}_{2}^{2}-15{h}_{1}^{4}{h}_{2}+{h}_{1}^{6}\\ 7!\mathcal{S}_{7}(n) &=& 720{h}_{7}-840{h}_{1}{h}_{6}-504{h}_{2}{h}_{5}+504{h}_{1}^{2}{h}_{5}-420{h}_{3}{h}_{4}+630{h}_{1}{h}_{2}{h}_{4}\\ &&-210{h}_{1}^{3}{h}_{4}+280{h}_{1}{h}_{3}^{2}+210{h}_{2}^{2}{h}_{3}-420{h}_{1}^{2}{h}_{2}{h}_{3}\\ &&+70{h}_{1}^{4}{h}_{3}-105{h}_{1}{h}_{2}^{3}+105{h}_{1}^{3}{h}_{2}^{2}-21{h}_{1}^{5}{h}_{2}+{h}_{1}^{7}\\ 8!\mathcal{S}_{8}(n) &=& -5040{h}_{8}+5760{h}_{1}{h}_{7}+3360{h}_{2}{h}_{6}-3360{h}_{1}^{2}{h}_{6}+2688{h}_{3}{h}_{5}\\ &&-4032{h}_{1}{h}_{2}{h}_{5}+1344{h}_{1}^{3}{h}_{5}+1260{h}_{4}^{2}-3360{h}_{1}{h}_{3}{h}_{4}\\ &&-1260{h}_{2}^{2}{h}_{4}+2520{h}_{1}^{2}{h}_{2}{h}_{4}-420{h}_{1}^{4}{h}_{4}-1120{h}_{2}{h}_{3}^{2}\\ &&+1120{h}_{1}^{2}{h}_{3}^{2}+1680{h}_{1}{h}_{2}^{2}{h}_{3}-1120{h}_{1}^{3}{h}_{2}{h}_{3}+112{h}_{1}^{5}{h}_{3}\\ &&+105{h}_{2}^{4}-420{h}_{1}^{2}{h}_{2}^{3}+210{h}_{1}^{4}{h}_{2}^{2}-28{h}_{1}^{6}{h}_{2}+{h}_{1}^{8}\\ \end{array}$$

$\endgroup$
0
$\begingroup$

Expanding the right hand side of the identity given by achille hui we get ``a compact'' expression for the sum: \begin{eqnarray} {\mathcal S}_p(n) &=& \sum\limits_{m=1}^p \frac{(-1)^{-m+p} }{m!} \sum\limits_{p_1+p_2+\dots+p_m=p} \prod\limits_{q=1}^m \frac{H_{n-1}^{(p_q)}}{p_q} \\ &=& \frac{1}{1!} \frac{(-1)^{p-1}}{p} H^{(p)}_{n-1} + \frac{(-1)^{p-2}}{2!} \sum\limits_{p_1=1}^{p-1} \frac{1}{p_1 (p-p_1)} H_{n-1}^{(p_1)} H_{n-1}^{(p-p_1)} + \dots + \frac{1}{p!} H_{n-1}^p \end{eqnarray}

$\endgroup$
0
$\begingroup$

Suppose we seek to evaluate

$$S_n(m) = \sum_{1\le j_1 \lt j_2 \lt\cdots\lt j_n \le m-1} \prod_{q=1}^n \frac{1}{m-j_q}.$$

By way of enrichment let me point out that we can express this sum in terms of the cycle index $Z(P_n)$ of the unlabeled set operator $\mathfrak{P}_{=n}$ by applying the Polya Enumeration Theorem.

Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(P_n)$ very easily.

The sum is then given by $$Z(P_n)(Q_1+Q_2+\cdots+Q_{m-1})$$ evaluated at $Q_k = \frac{1}{m-k}.$

The Polya enumeration rule says to substitute as follows: $$a_l = Q_1^l + Q_2^l + \cdots + Q_{m-1}^l$$

in other words $$a_l = H_{m-1}^{(l)}$$

for a final answer of $${\large \bbox[5px,border:2px solid #00A000]{ \left.Z(P_n)\right|_{a_l = H_{m-1}^{(l)}}}}$$

For example we have $$Z(P_5) = \frac{1}{5!} \left({a_{{1}}}^{5}-10\,a_{{2}}{a_{{1}}}^{3}+20\,a_{{3}}{a_{{1}}}^{2} +15\,a_{{1}}{a_{{2}}}^{2}-30\,a_{{4}}a_{{1}} -20\,a_{{2}}a_{{3}}+24\,a_{{5}}\right)$$ and the substitution should now be clear.

$\endgroup$

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.