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

148 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.