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?
 A: 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.
