7
$\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$
6
  • $\begingroup$ There are typos in your configuration, should be $$n = 2 \to \begin{matrix}*2 & 0*\\0 & 1\end{matrix}, \quad n = 4 \to \begin{matrix} 4 & 0 & 0 & 0\\ 2 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ *0 & 2 & 0 & 0*\\ *0 & 0 & 0 & 1* \end{matrix}$$ BTW, the first few numbers of your sequences are $1,1,5,41,469,6889$ and it matches the one on OEIS A032188. $\endgroup$ Dec 13, 2016 at 5:34
  • $\begingroup$ @achillehui Thank you for the typos, I have corrected it. As for the sequence you are talking about, it seems to give some informations about a generating function, but I am not familiar with this tool. Is it possible to deduce a bound for my series from your link (I do not see how)? $\endgroup$
    – Nicolas
    Dec 13, 2016 at 10:03
  • $\begingroup$ I don't know what you can get from the link but I'm working on a closed form expression of your series. If I didn't make any mistake, the radius of convergence of $\sum_{n=0}^\infty S_n \frac{x^{n+1}}{(n+1)!}$ is $1 - \log(2)$, this implies $\frac{S_n}{(n+1)!} \sim o( r^n )$ for any $r > \frac{1}{1 - \log(2)}$. $\endgroup$ Dec 13, 2016 at 11:33
  • $\begingroup$ @achillehui If you could get a closed form, it would be great! My goal is to prove that the series in $x$ converges for some $x\in\mathbb{C}$. $\endgroup$
    – Nicolas
    Dec 13, 2016 at 13:22
  • $\begingroup$ @Nicolas If both MO accounts appearing on this question belong to you, you can try to merge them. Related post on this site's meta: Announcement: New User Merge Policy/Tool. $\endgroup$ Jan 4, 2017 at 16:46

2 Answers 2

8
+350
$\begingroup$

First, we will transform $S_n$ to a form easier to manipulate.

Let $C \subset \mathbb{C}$ be a circle of radius $r \ll 1$ centered at $0$. For any $n \in \mathbb{N}$, $m \in \mathbb{N}^n$, we can single out those $m \in \mathfrak{M}_n$ with help of contour integrals of the form:

$$\delta_n(m) \stackrel{def}{=} \frac{1}{2\pi i} \oint_{C} s^{\sum_{k=1}^n k m_k} \frac{ds}{s^{n+1}} = \begin{cases}1, & m \in \mathfrak{M}_n\\ 0, & \text{ otherwise }\end{cases}$$ Together with following integral representation of factorial:

$$n! = \Gamma(n+1) = \int_0^\infty t^n e^{-t}dt$$ We have

$$\begin{align} S_n &= \sum_{m \in \mathbb{N}^n} \delta_n(m) \int_0^\infty \prod_{k=1}^n \frac{1}{m_k!} \left(\frac{t}{k+1}\right)^{m_k} t^n e^{-t} dt\\ &= \frac{1}{2\pi i}\sum_{m \in \mathbb{N}^n} \oint_C \left[\int_0^\infty \prod_{k=1}^n \frac{1}{m_k!} \left(\frac{ts^k}{k+1}\right)^{m_k} \left(\frac{t}{s}\right)^ne^{-t} dt \right] \frac{ds}{s}\\ &= \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \prod_{k=1}^n \left(\sum_{m_k=0}^\infty \frac{1}{m_k!} \left(\frac{ts^k}{k+1}\right)^{m_k}\right) \left(\frac{t}{s}\right)^ne^{-t} dt \right] \frac{ds}{s}\\ &= \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \prod_{k=1}^n \exp\left(\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^ne^{-t} dt \right] \frac{ds}{s}\\ &= \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \exp\left(\sum_{k=1}^n\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^ne^{-t} dt \right] \frac{ds}{s}\\ &\stackrel{\color{blue}{[1]}}{=} \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \exp\left(\sum_{k=1}^\infty\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^ne^{-t} dt \right] \frac{ds}{s}\\ &= \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \exp\left[-t\left(\frac{\log(1 - s)}{s} + 2\right)\right]\left(\frac{t}{s}\right)^n dt \right] \frac{ds}{s}\tag{*1}\\ \end{align} $$ Next, let

  • $S(x) \stackrel{def}{=} \sum_{n=0}^\infty S_n \frac{x^n}{n!}$ be the EGF (exponential generating function) for $S_n$.
  • $\Delta(x) = \sum_{n=0}^\infty S_n \frac{x^{n+1}}{(n+1)!}$ be the series we want to study its convergence.

They are related by the relation $\Delta(x) = \int_0^x S(t) dt$.
For any $x$ with $|x| \ll r$, $(*1)$ implies

$$\begin{align} S(x) &= \frac{1}{2\pi i}\oint_C \left[\int_0^\infty \exp\left[-t\left(\frac{\log(1 - s)}{s} + 2 - \frac{x}{s}\right)\right] dt \right] \frac{ds}{s}\\ &= \frac{1}{2\pi i} \oint_C \frac{ds}{\log(1-s) + 2s - x} \end{align} $$ Change variable to $y = -\log(1-s) \iff s = 1 - e^{-y}$. When $r$ is small, the image of $C$ in $y$-space is close to circle $C$. We can deform the contour back to $C$ without changing the integral. This leads to

$$S(x) = \frac{1}{2\pi i}\oint_C \frac{dy}{P(x,y)} \quad\text{ where }\quad P(x,y) = (2-x-y)e^y - 2 $$ Under the condition $|x| < |y| = r \ll 1$, we have

$$P(x,y) \approx (2 - x - y) (1 + y + O(r^2)) - 2 \approx y - x + O(r^2)$$

This means for fixed $x$ and as a function in $y$, $P(x,y)$ has only one root inside $C$. Furthermore, the root in $y$ is close to $x$. Let $\eta$ be that root, we have

$$\begin{align} P(x,\eta) = 0 &\iff (2-x-\eta)e^\eta - 2 = 0 \iff (\eta + x - 2)e^{\eta + x - 2} = -2e^{x-2}\\ & \implies 2 - x - \eta = -W(-2e^{x-2}) \end{align} $$ where $W(z)$ is a branch of the Lambert-W function. In terms of $\eta$, we have

$$\begin{align} S(x) &= \text{Res}_{y=\eta}\left(\frac{1}{P(x,y)}\right) = \left.\frac{1}{\frac{\partial}{\partial y}P(x,y)}\right|_{y=\eta} = \frac{1}{(1 - x - \eta)e^\eta}\\ &= \frac{2-x-\eta}{2(1-x-\eta)} = \frac{W(-2e^{x-2})}{2(1+W(-2e^{x-2}))} \end{align} $$

Since $S(0) = 1$, we need to choose a branch of Lambert W function with $W(-2e^{-2}) = -2$. The correct branch is the "lower branch" described in above wiki link. It is usually denoted as $W_{-1}(\cdot)$. In terms of it, we find

$$S(x) = \frac{W_{-1}(-2e^{x-2})}{2(1+W_{-1}(-2e^{x-2}))}$$

Notice the branches of Lambert W function satisfies ODE $$z\frac{d}{dz}W(z) = \frac{W(z)}{1+W(z)}\tag{*2}$$ We can integrate $(*2)$ and deduce a closed form expression for $\Delta(x)$: $$\Delta(x) = \frac12 \int_0^x \left[ z\frac{dW_{-1}(z)}{dz} \right]_{z=-2e^{t-2}} dt = 1 + \frac12 W_{-1}(-2e^{x-2})\tag{*3}$$

$W_{-1}(z)$ has two branch cuts, one terminated at $z = -\frac1e$, the other at $z = 0$. The closest singularity of $\Delta(x)$ to origin is located at $x = 1 - \log(2)$. As a result, $r_0$, the radius of convergence of the power series expansion of $\Delta(x) = \sum\limits_{n=0}^\infty S_n\frac{x^{n+1}}{(n+1)!}$, $r_0$ equals to $1 - \log(2)$. A corollary of this is$\color{blue}{{}^{[2]}}$

$$\frac{S_n}{(n+1)!} \sim o(\rho^n)\quad\text{ for any }\; \rho > \frac{1}{1-\log(2)} \approx 3.258891353270929$$

As a double check, we evaluate the power series expansion of $\Delta(x)$ using following command Series[1+1/2*LambertW[-1,-2*Exp[x-2]],{x,0,8}] on WA (wolfram alpha). WA returns

$$\begin{align} \Delta(x) = & x+\frac{{x}^{2}}{2}+\frac{5\,{x}^{3}}{6}+\frac{41\,{x}^{4}}{24}+\frac{469\,{x}^{5}}{120}+\frac{6889\,{x}^{6}}{720}\\ & +\frac{24721\,{x}^{7}}{1008}+\frac{2620169\,{x}^{8}}{40320}+\frac{64074901\,{x}^{9}}{362880} + \cdots \end{align}$$ Translate back to $S_n$, this is equivalent to

$$( S_0,S_1,\ldots ) = (1, 1, 5, 41, 469, 6889, 123605, 2620169, 64074901,\ldots )$$ For $n \le 5$, I have checked by hand this is indeed the correct value.

An OEIS search return the sequence OEIS A032188. Up to $n = 18$, I've verified the $S_n$ extract from expansion of $(*3)$ matches the numbers on OEIS. Look at references there and see whether there is anything useful for your purposes.

Notes

  • $\color{blue}{[1]}$ - As a function of $s$, $$\exp\left(\sum_{k=1}^n\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^n\frac{e^{-t}}{s} = \frac{1}{s^{n+1}}A(s)\quad\text{ and }\quad \exp\left(\sum_{k=n+1}^\infty\frac{ts^k}{k+1}\right) = 1 + s^{n+1}B(s) $$ where $A(s), B(s)$ are analytic over the disc bounded by $C$. This implies $$\exp\left(\sum_{k=1}^\infty\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^n\frac{e^{-t}}{s} = \exp\left(\sum_{k=1}^n\frac{ts^k}{k+1}\right) \left(\frac{t}{s}\right)^n\frac{e^{-t}}{s} + A(s)B(s)$$ Changing the upper bound in the sum within the exponent from $n$ to $\infty$ modifies the integrand by a function analytic over the disc bounded by $C$. The value of the contour integral over $C$ remains the same.

  • $\color{blue}{[2]}$ - A more detailed analysis suggests for large $n$, $S_n$ has following approximation: $$S_n \approx \frac{(2n)!}{\sqrt{8r_0}n!(4r_0)^n}\left( 1 - \frac{r_0}{6(2n-1)} + \cdots \right)\quad\text{ where }\quad r_0 = 1 - \log(2)$$ For $n$ as small as $4$, this formula gives a relative error below $10^{-4}$ (checked against numbers from OEIS). The leading behavior of coefficients of $\Delta(x)$ should be: $$\frac{S_n}{(n+1)!} \sim O\left(\frac{r_0^{-n}}{\sqrt{8\pi r_0} n^{3/2}}\right)$$

$\endgroup$
7
  • $\begingroup$ Absolutely amazing! This is clear and well done!! I just have one question: in the long equation $(*1)$, why can we modify the series of $ts^k/(k+1)$ in the exponential in a sum on $0\leq n\leq+\infty$? $\endgroup$
    – Nicolas
    Dec 13, 2016 at 15:08
  • $\begingroup$ @Nicolas When you expand $\exp\left(\sum\limits_{k=n+1}^\infty \frac{ts^k}{k+1}\right)$ as a power series in $s$, you get something of the form $1 + \sum\limits_{k=n+1}^\infty \alpha_k s^k$. Aside from the constant term, all remaining terms contain a factor $s^{n+1}$. This is enough to cancel the singular factor $\frac{1}{s^{n+1}}$ in the rest of the integrand. Replacing the sum from $0\to n$ to $0\to\infty$ changes the integrand by a function analytic inside $C$. The value of contour integral over $C$ remains the same. $\endgroup$ Dec 13, 2016 at 19:18
  • $\begingroup$ Of course! I forgot the $s^{-(n+1)}$ term. Ok, now it is perfect to me, I do thank you for your efforts and for the time you've spent to write this answer. $\endgroup$
    – Nicolas
    Dec 13, 2016 at 19:36
  • $\begingroup$ @achillehui: Clear, concise and instructive! Very nice! (+1) $\endgroup$
    – epi163sqrt
    Dec 13, 2016 at 21:37
  • $\begingroup$ @achillehui Almost one year later, I have another question about the long equation (*1): in the third line, you enter the sum of multi indices and exchange it with the product in the integral. I understand the exchange with the product (this is the Cauchy product formula) but I do not see why you can enter the sum in the integral. Dominated convergence theorem seems to be the argument to use, but one needs to show that the series of the integral of the modulus converges, which is quite similar to show the convergence of $S_n$! Have you got any argument to propose? Thanks in advance. $\endgroup$
    – Nicolas
    Sep 26, 2017 at 17:58
1
$\begingroup$

Here is a solution of a related problem, followed by a recommendation for the original problem. It would be much simpler if your sum did not have the $n$ in $(n+|m|)!\,$. In that case, we could look at the related sum $$t_n=\sum_{m\in {\mathfrak{M} }_n}\frac{|m|!}{m!}\prod_{k=1}^n(k+1)^{-m_k}.$$ The sum for the $t$'s comes from a product of exponential generating functions. Because of the factor of $(k+1)^{-m_k}$ in $t_n$ and the term $k\,m_k$ in ${\mathfrak{M} }_n$, we must look at the series $$1+\frac{\left(\frac{x^k}{k+1}\right)^1}{1!} +\frac{\left(\frac{x^k}{k+1}\right)^2}{2!} +\frac{\left(\frac{x^k}{k+1}\right)^3}{3!} +\cdots=\exp\left(\frac{x^k}{k+1}\right).$$ From multiplying these exponential generating functions, we get $$t_n=\left[\frac{x^n}{n!}\right]\prod_{k\ge1}\exp\left(\frac{x^k}{k+1}\right).$$ This product turns out to have a nice closed form: \begin{eqnarray*} % \nonumber to remove numbering (before each equation) \prod_{k\ge1}\exp\left(\frac{x^k}{k+1}\right) &=& \exp\left(\sum_{k\ge1}\frac{x^k}{k+1}\right) \\ &=& \exp\left(\frac1x\biggl(\log\bigl(\frac1{1-x}\bigr)-x\bigr)\right) \\ &=& (1-x)^{-x}/\mathrm{e} . \end{eqnarray*} The smallest singularity of $(1-x)^{-x}$ is at 1, so a crude approximation would be $$[x^n](1-x)^{-x}\approx1^n=1$$ and $$t_n=\left[\frac{x^n}{n!}\right](1-x)^{-x}/\mathrm{e}\approx n!/\mathrm{e}.$$ Certainly, a finer analysis of the singularity of $(1-x)^{-x}$ would give a better approximation and perhaps produce the power $\alpha$ you're seeking.

Now, back to the original problem. It's always the case that $|m|\le n$, so a rough bound on $s_n$ would be $$s_n\le(2n)!t_n\le(2n)!\, .$$ This bound is worse than the hope you expressed, but perhaps good enough for your eventual purposes or perhaps a start for finer analysis.

$\endgroup$
3
  • $\begingroup$ Thank you for your interest and your efforts! Could you please explain the link with the exponential generating functions (I am not familiar with generating functions)? Also, I do not understand why we can rewrite $t_n$ with the terms $x^n/n!$ and the product of exponentials (there was no $x$ in your original $t_n$)? Thanks in advance. $\endgroup$
    – Nicolas
    Dec 12, 2016 at 22:54
  • $\begingroup$ @Nicolas There are a zillion places to learn about generating functions. A couple of my favorites are Concrete Mathematics (chapter 7) and Generatingfunctionology (the first couple chapters). Generating functions form a really powerful tool, and they're well worth the time to sink your teeth into. After digesting a chapter or two of those texts, this answer might be more meaningful. $\endgroup$
    – Rus May
    Dec 13, 2016 at 4:02
  • $\begingroup$ Ok thank you for the reference. Unfortunately, I do not have much time to read it for now... Anyway, good start point here! $\endgroup$
    – Nicolas
    Dec 13, 2016 at 10:32

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.