# Flajolet & Sedgewick: Asymptotic behavior of "super-necklaces"

In Flajolet and Sedgewick's Analytic Combinatorics pp. 261 (Chapter IV Note IV.28), the authors state that

\begin{align} [z^n]\ln \left(\frac{1}{1- \ln \frac{1}{1-z}}\right) \sim \frac{1}{n} (1-e^{-1})^{-n} \tag{1} \end{align}

where $$S(z) = \ln \left(\frac{1}{1-\ln \frac{1}{1-z}}\right)$$ is the EGF of the "super-necklaces", which is defined as

\begin{align} \mathcal{S} = CYC \circ CYC(\mathcal{Z}) \end{align}

I can't reach $$(1)$$ as $$S(z)$$ cannot be expressed as a rational function $$\frac{f(z)}{g(z)}$$. Also, the derivative of $$S(z)$$ still consists of the factor $$\left(1-\ln \frac{1}{1-z}\right)$$, which is $$0$$ at the pole $$1-e^{-1}$$. (A usual method to solve this kind of problems is to find the derivative $$g'(z_0)$$, where $$z_0$$ is the pole of $$S(z)$$. But it looks not applicable in this problem.)

Is there any method to solve the problem?

• shouldn't it be possible to solve this just by using integration by parts (with a suitable chosen contour) and application of the residue theorem to the resulting integral (boundary term vanishs, since contour is closed)? Commented Sep 14, 2022 at 8:29
• Yes, my original thinking is to apply the residue theorem on the poles. However, I found problem in finding the residue. The pole is obviously at $(1-e^{-1}$. But the derivative of the function always left the factor $\left(1-\ln \frac{1}{1-z}\right)$ at the denominator, which turns out to be zero at $(1-e^{-1})$. That's the problem in this method. Commented Sep 15, 2022 at 12:06
• WolframAlpha spits them out pretty smoothly, i will see what i can do by hand Commented Sep 19, 2022 at 8:21
• if you integrate by parts first, you can apply the usual residue formula for simple poles, since $f'(1-1/e)$ becomes finite ($f(z)=(\log(1-1/z)-1)(z-1)$ is the denominator after integragting by parts). Commented Sep 19, 2022 at 19:52

If you perform the expansion near $$z\to \rho$$ you end up with (if I'm not mistaken) $$S(z) = \ln(\frac 1e) + \ln(\frac 1 {\rho-z}) + O(\rho-z)$$.

I obtained this by simply setting $$h = \rho-z$$ then using Taylor expansion of $$\ln$$ keeping in mind that $$z\to 0$$. Namely

$$S(z) = \ln(\dfrac 1 {1- \ln(\frac {1}{e^{-1} +h})}) = \ln(\dfrac 1 {1-\ln e + \ln(1+eh)}) = \ln(\dfrac 1 {\ln(1+eh)}) = \ln(\dfrac 1 {eh + O(h^2)}) = \ln(\frac 1e) + \ln(\frac 1 h)+\ln(\frac 1 {1+O(h)}) = QED$$ The results of chapter VI (transfer theorems) allow you to work such problems out when you don't have an exactly meromorphic function anymore but only an asymptotic estimate. Basically your coefficients will be asymptotic to the coefficients of the leading term.

There are some technical conditions ($$\Delta$$-analyticity) that you have to check, which is not a problem in your case, where your function should be defined on a slit disk).

• May I clarify a bit the details? (As I've not yet reached Chap. VI in my study...) $\rho$ is the singularity, $\rho = 1 - e^{-1}$. From your expansion, \begin{align} S(z) &= \ln \left(\frac{1}{e}\right) + \ln \left(\frac{1}{\rho}\right) + \ln \left(\frac{1}{1-\frac{z}{\rho}}\right) + O(\rho - z) \\ &= -\ln e -\ln \rho + \sum_{k=1}^{\infty} \frac{1}{k} \left(\frac{z}{\rho}\right)^k + O(\rho - z) \end{align} Hence, \begin{align} [z^n]S(z) &\sim \frac{1}{n} \frac{1}{\rho ^k} \\ &= \frac{1}{n} \left(1 - e^{-1}\right)^{-n} \end{align} Commented Sep 13, 2022 at 2:57
• Sorry, a typo. Should be: \begin{align} [z^n]S(z) \sim \frac{1}{n} \frac{1}{\rho ^n} = \frac{1}{n} \left(1-e^{-1}\right) ^{-n} \end{align} But I still can't figure out how to get your expansion of $S(z)$. Could you elaborate more on the details? Thanks. Commented Sep 13, 2022 at 3:48
• Edited my answer with more detail. Commented Sep 13, 2022 at 12:12
• Thank you very much. It's clear. Commented Sep 14, 2022 at 2:44
• My pleasure! Enjoy learning from that book and welcome to the cult ;) Commented Sep 16, 2022 at 14:16