3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Here is a suggestion, spurred by a vague recollection of similar work done long ago. There may be a way to use AM-GM inequality to bound the expression. I feel optimistic though that alpha will be small. Gerhard "It's That Time Of Year" Paseman, 2016.12.12. $\endgroup$ – Gerhard Paseman Dec 12 '16 at 23:52
  • 2
    $\begingroup$ (1) By $\mathbb{N}$ you mean non-negative integers; (2) The sets $\mathfrak{M}_n$ is just the set of integer partitions of $n$; (3) Your example for $n=2$ has a typo: $2 0$ and $0 1$. $\endgroup$ – T. Amdeberhan Dec 13 '16 at 1:05
  • 1
    $\begingroup$ This is better discussed in the language of integer partitions. Generating functions may help. Where did this problem come from? $\endgroup$ – Pat Devlin Dec 13 '16 at 2:49
  • $\begingroup$ @GerhardPaseman Thanks for the idea, I will have a try! $\endgroup$ – Nicolas Dec 13 '16 at 9:43
  • 2
    $\begingroup$ A very good answer has been provided here: math.stackexchange.com/questions/2049773/…. $\endgroup$ – Nicolas Dec 13 '16 at 23:01
2
$\begingroup$

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.$$

$\endgroup$
2
$\begingroup$

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}}$

$\endgroup$
0
$\begingroup$

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

adjacency matrix of  weighted digraph

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\, . $$

$\endgroup$
  • $\begingroup$ The coefficients in the question are not multinomials, they are multinomials times $\frac{(n+m_1+...+m_n)!}{(m_1+...+m_n)!}$ $\endgroup$ – მამუკა ჯიბლაძე Dec 14 '16 at 17:14
  • $\begingroup$ You right. I wanted to show a different attitude to this kind of series. The answer was edited by your tip. Thanks. $\endgroup$ – Amin235 Dec 14 '16 at 19:43

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.