A sum over partitions involving "subpartitions"

Question

Consider the following sum over partitions of $n$:

$$ S(n)=\sum_{\substack {j_1,\dots,j_n\geq 0\\j_1+2j_2+\dots+nj_n=n}} \prod_{t=1}^n \frac{1}{j_t!t^{j_t}}f_t(j_1,\dots,j_t),$$

where

$$ f_t(j_1,\dots,j_t)=\begin{cases}\frac{j_t}{j_t+1}\,&\textrm{if } j_1+2j_2+\dots+(t-1)j_{t-1}=t-1 \\1 \,&\textrm{otherwise}\end{cases}.$$

I have strong numerical evidence that

$$ S(n)=\frac{1}{n+1},$$

but I cannot prove it, I was wondering if anyone could give me ideas.

Some observations: I wasn't able to compute it using a simple generating function, since I would need $f_t(j_1,\dots,j_t)$ to be a function only of $j_t$.

The function $$f(j_1,\dots, j_n)=\prod_{t=1}^n f_t(j_1,\dots,j_t)$$ can also be intepreted as a function of the cycle structure of a permutation depending on which "subpartitions" $j_1,\dots, j_n$ contains, or on the invariant subsets of $\{1,\dots, n\}$ under the permutations with the cycle structure given by the partition. $S(n)$ can be seen as the average of $f$ over the permutation group, since the $\prod_{t=1}^n \frac{1}{j_t!t^{j_t}}$ is the probability of drawing a permutation with $j_k$ $k-$cycles in its decomposition.

Ideally, I would like to compute, or at least bound

$$ S(n,x)=\sum_{\substack {j_1,\dots,j_n\geq 0\\j_1+2j_2+\dots+nj_n=n}} \prod_{t=1}^n \frac{x^{j_t}}{j_t!t^{j_t}}f_t(j_1,\dots,j_t),$$

for $x>0$, but I don't have a good conjecture on the form of this sum, except for $x=1$.

Answer 1

Consider the generating functions $$ R_k(u) = \sum_{j_1,\ldots,j_k\geq 0} u^{j_1 + 2 j_2 + \cdots + k j_k} \prod_{t=1}^k \frac 1{j_t! t^{j_t}} f_t(j_1,\ldots,j_t). $$ I will prove by induction on $k$ that $$ R_k(u) = \frac 1 u + (1-\frac 1u) \exp(u+\frac {u^2}2+\cdots+\frac {u^k}k) = \frac {u^k}{k+1} + O(u^{k+1}). $$

Note that the first formula implies the second one. Indeed, we have $$ (1-\frac 1u) \exp(u+\frac {u^2}2+\cdots+\frac {u^k}k+\frac {u^{k+1}}{k+1}+\cdots) = (1-\frac 1u) \exp(-\ln(1-u)) = -\frac 1u. $$ Terms with $u^{k+2}$ and higher do not contribute to $u^k$ and lower, so we get $$ (1-\frac 1u) \exp(u+\frac {u^2}2+\cdots+\frac {u^k}k+\frac {u^{k+1}}{k+1}) = -\frac 1u +O(u^{k+1}) $$ and $$ (1-\frac 1u) \exp(u+\frac {u^2}2+\cdots+\frac {u^k}k) = -\frac 1u \exp(-\frac {u^{k+1}}{k+1}) +O(u^{k+1}) = -\frac 1u +\frac {u^k}{k+1}+O(u^{k+1}). $$

The base of induction $k=1$ is rather easy, we get $$R_1 = \sum_{j\geq 0}\frac {u^j}{j!} \frac j{j+1}$$ $$=\exp(u) - \sum_{j\geq 0}\frac {u^j}{(j+1)!} = \exp(u) + \frac {\exp(u)-1}u$$ and the statement follows.

To prove the induction step $k\to (k+1)$ observe that $$ R_{k+1}(u) = R_k(u) \exp(\frac {u^{k+1}}{k+1}) - u^k( {\rm Coeff.~of~}R_k{\rm~at~}u^k) \Big(\sum_{j\geq 0} \frac {u^{j(k+1)}}{(j+1)! (k+1)^j}\Big) $$ (using the induction assumption) $$= R_k(u) \exp(\frac{u^{k+1}}{k+1}) -\frac {u^k}{k+1} \Big(\frac{\exp(\frac {u^{k+1}}{k+1})-1}{\frac {u^{k+1}}{k+1}}\Big) $$ $$ =(R_k(u)-\frac 1u)\exp(\frac {u^{k+1}}{k+1}) + \frac 1u $$ $$ =\frac 1 u + (1-\frac 1u) \exp(u+\frac {u^2}2+\cdots+\frac {u^{k+1}}{k+1}). $$

It remains to observe that the coefficient of $R_n(u)$ at $u^n$ is exactly the original formula.

Answer 2

This is just an extended comment providing an alternative view at $S(n)$, which (I hope) may lead to a solution.

Notice that $f_t(j_1,j_2,\dots,j_t) = 1-\frac{\delta_{j,t}}{1+j_t}$, where $$\delta_{j,t} := \big[j_1+2j_2+\dots+(t-1)j_{t-1} = t-1\big]$$ is an Iverson bracket.

Let $\bar n:=\{1,2,\dots,n\}$ and for a given partition exponents $j=(j_1,\dots,j_n)$ with $j_1 + 2j_2+\dots+nj_n=n$, define $J(j) := \{t\in\bar n\,:\,\delta_{j,t}=1\}$. Then \begin{split} (n+1)! S(n)&=(n+1)!\sum_{j:\ j_1 + 2j_2+\dots+nj_n=n} \prod_{t=1}^n \frac{1}{j_t!t^{j_t}} \sum_{T\subseteq J(j)} (-1)^{|T|} \prod_{t\in T} \frac1{j_t+1} \\ &= \sum_{T\subseteq \bar n} (-1)^{|T|} \sum_{j:\ j_1 + 2j_2+\dots+nj_n=n\atop J(j)\supseteq T} \prod_{t=1}^n \frac{(n+1)!}{(j_t + [t\in T])!\,t^{j_t}}. \end{split} The last formula may be viewed as application of the inclusion-exclusion principle under a suitable combinatorial interpretation of its terms, which then would likely imply the needed $(n+1)!S(n)=n!$ out of the box. Unfortunately, I was not able to find such an interpretation so far, but have a gut feeling it's out there.