# Recurrence relation asymptotics

A continuation from my two previous posts:

I have got the following recurrence which describes polynomials:

$$C_n(a) = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} a^{t(n-t)} C_t(a)$$ where $C_1(a)=C_0(a) = 1$. The ultimate goal is to prove (this is the conjecture) that these polynomials tend to 1 pointwise for $0 \leq a < 1$.

What I got so far, is the generation function approach. By denoting $A_n(a) = a^{-\binom{n}{2}}C_n(a)$ I got the recurrence $$A_n(a) = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} a^{-\binom{n-t}{2}}A_t(a)$$, and so the generating function for $A_n(a)$ is $$F(x) = e^{g(x)}$$ where $g$ is itself a generating function $$g(x) = \sum\limits_{t=1}^{\infty} a^{-\binom{t}{2}}\frac{x^t}{t!}$$

My questions are

1) what's next in order to discover asymptotics of $C_n$? Evaluate poles of $F(z)$?

2) is the generating function $g(x)$ studied? I know that it is when the coefficient is $q^{\binom{n}{2}}$ for $0 < q < 1$, but in my case it is greater than 1.

Also, am I missing something which my help a lot?

Thank you!

UPDATE 1:

I was able to reformulate the problem as ($b > 1$) $$X_n(b) = \sum\limits_{t=0}^{n-1} \binom{n-1}{t} b^{\binom{n-t}{2}} X_t(b)$$ Prove that $|X_n(b) - b^{\binom{n}{2}}| \to 0$. So, here the generating function might work?

• If I follow your notation, you will recover $A_n(a) = \frac{1}{2\pi i} \oint_\gamma \frac{F(z)}{z^{n+1}} dz$, with $\gamma$ a small positively oriented circle about $z=0$. However, $g(z)$ and hence $F(z)$ seem entire to me. Hence they have no poles and likely have an essential singularity at $z=\infty$. So, sending the contour $\gamma$ to infinity is not going to pick up any poles and I don't see how it would help you estimate that integral. To use this method, I think, you would need a generating function $F(z) \to 0$ as $z \to \infty$ in some reasonable way. Feb 22, 2017 at 7:48
• @IgorKhavkine SInce $0\le a\lt 1$, if seems to me that $g(x)$ is not convergent for $x\ne 0$. Feb 22, 2017 at 10:35
• @BrendanMcKay, ah, you are right! I mistakenly estimated in my head that the $1/t!$ factor would dominate. In that case a naive application of the contour method will still not work because there is no analytic function $F(z)$ to integrate. :-/ Feb 22, 2017 at 10:42
• One thing to notice is that $C_n(1)$ is the $n$-th Bell number (oeis.org/A000110). I feel that there is a combinatorial interpretation waiting to be found here. Feb 22, 2017 at 10:55

## 1 Answer

OP didn't say where the problem came from, so maybe I am just reverse-engineering it here. If $P$ is a partition of a finite set $X$, define $\kappa(P)$ to be the number of pairs $x,y\in X$ such that $x$ and $y$ are in different cells of the partition.

Then $$C_n(a) = \sum_{P\in\mathbb{P}_n} a^{\kappa(P)},$$ where $\mathbb{P}_n$ is the set of all partitions of $\lbrace 1,\ldots,n\rbrace$. It is fairly easy to see how this satisfies the recurrence (the term $t$ corresponds to element $n$ being in a cell of size $n-t$).

The OP's conjecture says that for $0\le a\lt 1$, this expression is dominated by the partition with one cell. I can see how to approach this by a fairly brute-force method, but there should be something slick.

For a partition $P$ with $k\ge 2$ cells, the minimum value of $\kappa(P)$ occurs when $P$ has $k-1$ cells of size 1 and one cell of size $n-k+1$. Namely, $\kappa(P)\ge \frac12(k-1)(2n-k)\ge \frac12 (k-1)n$. This is good enough to eliminate partitions with $k\ge k_0=k_0(a)$ cells, where $k_0$ is large enough that $a^{(k_0-1)/2}k_0\lt 1$. For partitions with fewer than $k_0$ cells, a more precise method is needed.

For $2\le k\lt k_0$ it seems good enough to monitor the number of singletons in partitions. When there are lots of singletons there are fewer partitions, and when there are few singletons the value of $\kappa$ is greater. But I've got 5 mins to be in bed before midnight so if someone else wants to finish this, feel free.

• Thank you for your post! This does not look like reverse-engineering to me (at least on the first glance). This reccursion appeared as a subproblem. I'll try to work on this approach more and report the results. Feb 24, 2017 at 2:57