3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Igor Khavkine Feb 22 '17 at 7:48
  • $\begingroup$ @IgorKhavkine SInce $0\le a\lt 1$, if seems to me that $g(x)$ is not convergent for $x\ne 0$. $\endgroup$ – Brendan McKay Feb 22 '17 at 10:35
  • $\begingroup$ @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. :-/ $\endgroup$ – Igor Khavkine Feb 22 '17 at 10:42
  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Feb 22 '17 at 10:55
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Eugene Feb 24 '17 at 2:57

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.