Computation of a series

Question

NOTATIONS.

Let $n\in\mathbb{N}$. We define the sets $\mathfrak{M}_{0}:=\emptyset$ and \begin{align} \mathfrak{M}_{n}&:=\left\{m=\left(m_{1},m_{2},\ldots,m_{n}\right)\in\mathbb{N}^{n}\mid1m_{1}+2m_{2}+\ldots+nm_{n}=n\right\}&\forall n\geq1 \end{align} and we use the notations: \begin{align} m!&:=m_{1}!m_{2}!\ldots m_{n}!,&|m|&:=m_{1}+m_{2}+\ldots+m_{n}. \end{align}

QUESTION.

I want to evaluate or just bound with respect to $n$ the series \begin{align} S_{n}&:=\sum_{m\in\mathfrak{M}_{n}}\frac{\left(n+\left|m\right|\right)!}{m!}\ \prod_{k=1}^{n}\left(k+1\right)^{-m_{k}}. \end{align} My hope is that $S_{n}\leq n!n^{\alpha}$ with $\alpha$ independant of $n$.

BACKGROUND.

In order to build an analytic extension from a given real-analytic function, I had to use the Faà di Bruno's formula for a composition (see for example https://en.wikipedia.org/wiki/Faà_di_Bruno%27s_formula). After some elementary computations, my problem boils down to show the convergence of \begin{align} \sum_{n=0}^{+\infty}\frac{x^{n+1}}{(n+1)!}\sum_{m\in\mathfrak{M}_{n}}\frac{\left(n+\left|m\right|\right)!}{m!}\ \prod_{k=1}^{n}\left(k+1\right)^{-m_{k}} \end{align} where $x\in\mathbb{C}$ is such that the complex modulus $|x|$ can be taken as small as desired (in particular, we can choose $|x|<\mathrm{e}^{-1}$ to kill any $n^{\alpha}$ term from the bound on $S_{n}$).

SOME WORK.

It is clear that we have to to understand the sets $\mathfrak{M}_{n}$ in order to go on (whence the tag "combinatorics"). So I tried to see what were these sets:

• for $n=2$ : \begin{array}{cc} 2&0\\ 0&1 \end{array}
• for $n=3$ : \begin{array}{ccc} 3&0&0\\ 1&1&0\\ 0&0&1 \end{array}
• for $n=4$ : \begin{array}{cccc} 4&0&0&0\\ 2&1&0&0\\ 1&0&1&0\\ 0&2&0&0\\ 0&0&0&1\\ \end{array}
• for $n=5$ : \begin{array}{ccccc} 5&0&0&0&0\\ 3&1&0&0&0\\ 2&0&1&0&0\\ 1&0&0&1&0\\ 1&2&0&0&0\\ 0&0&0&0&1\\ 0&1&1&0&0\\ \end{array}

Above, each line corresponds to an multiindex $m$, and the $k$-th column is the coefficient $m_{k}$. We see for example that the cardinal of $\mathfrak{M}_{n}$ becomes strictly greater than $n$ if $n\geq5$. Also, because I wanted to reorder the set of summation in $S_{n}$ into a the set of all multiindices $m$ such that $|m|=j$ for $1\leq j\leq n$, I tried to count given $j$ the number of $m$ such that $|m|=j$; when $n=10$, I counted $8$ multiindices $m$ with length $|m|=4$, so that this number can be greater than $n/2$. Another remark is that the number of multiindices $m$ such that $|m|=j$ becomes larger if $j$ is "about" $n/2$ - don't ask me what "about" means here, I just tried some example and saw this phenomenon.

Answer 1

Using $\frac1{k+1}<\frac1k$ and the notation $\sum im_i=\lambda\vdash n$ (equiv. $\lambda\in\mathfrak{M}_n$), begin estimating \begin{align} S_{n} <&\sum_{m\in\mathfrak{M}_{n}}\frac{\left(n+\left|m\right|\right)!}{m!}\ \prod_{k=1}^{n}k^{-m_{k}} =\sum_{\lambda\vdash n}\frac{n!}{m!\prod k^{m_k}}\frac{(n+\vert m\vert)!}{n!}. \end{align} Note that $\frac{n!}{m!\prod k^{m_k}}$ is the number of permutations $\pi\in \mathfrak{S}_n$ having cycle type $(m_1,\dots,m_n)$ and $\vert m\vert=\kappa(\pi)=\#$ of cycles in $\pi$. In light of this, \begin{align} S_n<\sum_{\pi\in\mathfrak{S}_n}\frac{(n+\kappa(\pi))!}{n!} =\sum_{j=1}^nc(n,j)\frac{(n+j)!}{n!}; \end{align} where $c(n,j)$ are the (unsigned) Stirling numbers of the first kind. On the other hand, the numbers $a_n:==\sum_{j=1}^nc(n,j)(n+1)\cdots(n+j)$ are listed on OEIS A052819 and there Vaclav Kotesovec provideda growth estimate $$a_n \qquad \sim \qquad (1+r)^n(2+r)^n\left(\frac{n}e\right)^n.$$ Combining this with Stirling approximation $n!\sim \sqrt{2\pi n}\left(\frac{n}e\right)^n$, we obtain $$\frac1{n+1}\frac{S_n}{n!} \qquad \sim \qquad \frac{\sqrt{2\pi n}}{n+1} (1+r)^n(2+r)^n$$ where $r=0.794862961852611133\cdot$. Hence, the desired convergence of your series can be achieved form small $x$.

REMARK. The above estimates can be improved although it is not necessary for your purpose. For example, there is an expected number of cycles in a permutation (regarding $\kappa(\pi)$) given by $$H_n=1+\frac12+\frac13+\cdots+\frac1n\sim \log n.$$

Answer 2

Your $S_n$ starts with $1,1,5,41,469,6889,123605,2620169,64074901,1775623081,54989743445,...$; this seems to be A032188 on OEIS (number of labeled circular-rooted trees with $n$ leaves). The link contains lots of information if so. In particular, asymptotics given there is $S_{n-1}\sim\frac{n^{n-1}}{2e^n(1-\log(2))^{n-\frac12}}$

Answer 3

Assume the companion matrix $C_m$ of order $m$, in the following form

$$ C_m=\left( \begin{array}{cccccc} u_1 &u_2 &\cdots& \cdots &u_{m-1} &u_m \\ 1 &0 &\cdots &\cdots &\cdots &0 \\ 0 &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ 0 &\cdots &\cdots &0 &1 &0 \\ \end{array} \right)_{m \times m} \, . $$ where $u_1 , u_2, \cdots ,u_m$ are indeterminates. Look at $C_m$ as an adjacency matrix of a weighted digraph. For example, the adjacency matrix of weighted digraph $C_6$ is as shown

Chen has seen the $n$th power of $C_m$ matrix as paths of length $n$ between nodes of weighted digraph. He has proved that

Theorem: Let the $(i,j)$ entry of the $n$th power of matrix $C_m$ called $c_{ij}^n$, then the combinatorial closed-form of $c_{ij}^n$, is in the following form

$$ c_{ij}^n=\sum_{(k_1,k_2,\cdots,k_m)} \frac{k_j+k_{j+1}+\cdots+k_m}{k_1+k_2+\cdots+k_m}\times \left( \begin{array}{c} k_1+\cdots+k_m \\ k_1,\cdots , k_m \end{array} \right) u_1^{k_1}\cdots u_m^{k_m} \, . $$ where the summation is over non-negative integers satisfying $$ k_1+2\, k_2+3\, k_3+\cdots + m\, k_m=n-i+j \, . $$ and the coefficients $k_i$ are defined $1$ when $n=i-j$.

A simple form of your question is special case of the mentioned theorem when $n=m$, $i=j=1$ and $u_t=\frac{1}{t+1}$, $1\leq t \leq m$. With these parameters , we have

$$ c_{11}^m=\sum_{(k_1,k_2,\cdots,k_m)} \left( \begin{array}{c} k_1+\cdots+k_m \\ k_1,\cdots , k_m \end{array} \right) 2^{-k_1}\, 3^{-k_2}\, \cdots {(m+1)}^{-k_m} \, . $$ where the summation is over non-negative integers satisfying $$ k_1+2\, k_2+3\, k_3+\cdots + m\, k_m=m \, . $$

For example, when we want to obtain $S_5$, first we should calculate the $5$th power of matrix $C_5$, with $u_t=\frac{1}{t+1}$, $1\leq t \leq 5$, as shown

$$ C_5={ \left( \begin {array}{ccccc} \frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\frac{1}{5}&\frac{1}{6}\\ \\ 1&0&0&0&0\\ \\ 0&1&0&0&0\\ \\ 0&0&1&0&0\\ \\ 0&0&0&1&0 \end {array} \right)}^5= \left( \begin {array}{ccccc} {\frac {521}{480}}&{\frac {2887}{4320}}& {\frac {439}{960}}&{\frac {527}{1800}}&{\frac {629}{4320}}\\ \\ {\frac {629}{720}}&{\frac {467}{720}}&{\frac {181 }{480}}&{\frac {43}{180}}&{\frac {17}{144}}\\ \\ {\frac {17}{24}}&{\frac {187}{360}}&{\frac {33}{80}}&\frac{1}{5}&{\frac {7}{72}}\\ \\ {\frac {7}{12}}&{\frac {5}{12}}&{\frac {13}{40}} &{\frac {4}{15}}&\frac{1}{12}\\ \\ \frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\frac{1}{5}&\frac{1}{6} \end {array} \right) $$

That results that

$$ S_5=c_{11}^5=\frac {521}{480}= 1.085416667\, . $$