# Sum of $\prod 1/n_i$ where $n_1,\ldots,n_k$ are divisions of $m$ into $k$ parts.

Fix $m$ and $k$ natural numbers. Let $A_{m,k}$ be the set of all partitions divisions of $m$ into $k$ parts. That is:

$$A_{m,k} = \left\{ (n_1,\ldots,n_k) : n_i >0, \sum_{i=1}^k n_i = m \right\}$$

We are interested in the following sum $s_{m,k}$:

$$s_{m,k} = \sum_{ (n_1,\ldots,n_k) \in A_{m,k} } \prod_{i=1}^k \frac{1}{n_i}$$

Can you find $s_{m,k}$ explicitly, or perhaps its generating function or exponential generating function?

EDIT: Since order matters in the $(n_1,\ldots,n_k)$ this is not exactly a partition.

• These sums satisfy the recurrence relation $$s_{m,k}=\sum_{n_k=1}^{m-k+1}\frac{s_{m-n_k,k-1}}{n_k}\;.$$ – joriki Feb 22 '13 at 21:29

I am not sure I understand the problem correctly, but $$g(z) = \left( \frac{z}{1} + \frac{z^2}{2} +\frac{z^3}{3} + \ldots + \frac{z^q}{q} + \ldots \right)^k = \left( \log \frac{1}{1-z} \right)^k$$ looks like a good candidate to me, so that $$s_{m,k} = [z^m] \left( \log \frac{1}{1-z} \right)^k.$$ This is the exponential generating function for a sequence of $k$ cycles containing a total of $m$ nodes, $$\mathfrak{C}(\mathcal{Z}) \times \mathfrak{C(\mathcal{Z})} \times \mathfrak{C(\mathcal{Z})} \times \cdots \times \mathfrak{C(\mathcal{Z})} = \mathfrak{C}^k(\mathcal{Z}) ,$$ so that $m! [z^m] g(z)$ gives the number of such sequences.
Since the components are at most $m$ we could truncate the inner logarithmic term at $z^m/m$, but I suspect the logarithmic form is more useful for asymptotics.
\eqalign{ & \ln \left( {{1 \over {1 - x}}} \right)^{\,q} \quad \left| {\;0 \le {\rm integer}\,{\rm }q} \right.\quad = \left( {\sum\limits_{1\, \le \,k_{\,1} } {{{x^{\,k_{\,1} } } \over {k_{\,1} }}} } \right)\left( {\sum\limits_{1\, \le \,k_{\,2} } {{{x^{\,k_{\,2} } } \over {k_{\,2} }}} } \right) \cdots \left( {\sum\limits_{1\, \le \,k_{\,q} } {{{x^{\,k_{\,q} } } \over {k_{\,q} }}} } \right) = \cr & = \sum\limits_{0\, \le \,j} {\left( {\sum\limits_{\scriptstyle 1\, \le \,k_{\,i} \atop \scriptstyle \,k_{\,1} \, + \,k_{\,2} \, + \, \cdots \, + \,k_{\,q} \, = \,j} {{1 \over {k_{\,1} k_{\,2} \cdots k_{\,q} }}} } \right)x^{\,j} } = \cr & = \sum\limits_{0\, \le \,j} {{{q!} \over {j!}}\left[ \matrix{ j \cr q \cr} \right]\,x^{\,j} } = x^{\,q} \sum\limits_{0\, \le \,j} {{{q!} \over {\left( {q + j} \right)!}}\left[ \matrix{ q + j \cr q \cr} \right]\,x^{\,j} } \cr}
where ${\left[ \matrix{ j \cr q \cr} \right]}$ indicates the (unsigned) Stirling Number of 1st kind.
The above deriving from the double expansion : $${1 \over {\left( {1 - x} \right)^{\,y} }} = \left\{ \matrix{ = \sum\limits_{0\, \le \,j} {\,\left( { - 1} \right)^{\,j} \left( \matrix{ - y \cr j \cr} \right)x^{\,j} } = \sum\limits_{0\, \le \,j} {{{\left( { - 1} \right)^{\,j} } \over {j!}}\,x^{\,j} \left( { - y} \right)^{\,\underline {\,j} } } = \sum\limits_{\scriptstyle 0\, \le \,k \atop \scriptstyle 0\, \le \,j} {{1 \over {j!}}\left[ \matrix{ j \cr k \cr} \right]\,x^{\,j} y^{\,k} } \hfill \cr = \exp \left( {y\ln \left( {{1 \over {1 - x}}} \right)} \right) = \sum\limits_{0\, \le \,k} {{{y^{\,k} } \over {k!}}\left( {\ln \left( {{1 \over {1 - x}}} \right)} \right)^{\,k} } \hfill \cr} \right.$$