7
$\begingroup$

This is a follow up to my recent question on the asymptotics of A003238. Lucia gave a fine answer to that question, but as I hinted the 'real' problem I have in mind is slightly different, and I've not been able to massage that answer into a solution for this case. On the other hand it feels like it should be easier or known how to handle the resulting problem, so here we are again.

Consider rooted trees where all vertices at the same level have the same number of children and this is $\geq 3$ except for leaves. If we let $s(n)$ denote the number of such trees with $n$ nodes then we get a sequence for $n \geq 1$:

1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, ...

Note the first 2 occurs at $n = 13$ corresponding to either a root with 12 children, or a root with three children, each of which has three children. Obviously, the $s$ sequence doesn't have an asymptotic form (since e.g. $s(p+1) = 1$ for all odd primes $p$). However, letting $$ S(x) = \sum_{n \leq x} s(n) $$ and rearranging the order of summation as in Lucia's solution gives: $$ S(n+1) = 1 + \sum_{d \geq 3} S(n/d) $$ (plus the obvious extra conditions, $S(0) = 0$, $S(x) = S(\lfloor x \rfloor)$.)

So, what are the asymptotics of $S$?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ My guess would be something on the order of $x^{\alpha}$ where $\alpha=1.58278\ldots$ is the solution to $\zeta(\alpha)-1-2^{-\alpha} = 1$. It should be easy (?) to show that $S(x)\le x^{\alpha+\epsilon}$ for large $x$, and $S(x) \ge x^{\alpha-\epsilon}$ for large $x$. $\endgroup$
    – Lucia
    Commented Mar 11, 2014 at 22:49
  • $\begingroup$ That suggestion for the exponent is certainly in strong agreement with a linear regression on the log-log scale. $\endgroup$
    – Michael Albert
    Commented Mar 11, 2014 at 22:56

1 Answer 1

Reset to default
3
$\begingroup$

I'd like to promote Lucia's comment to an answer if I could but apparently I can't. I'll just fill in a few of the details. The basic idea is to pretend that $S(x) = C x^{\alpha}$. Plug in to the recursion and ignore terms that are $o(x^{\alpha})$ and you get $\zeta(\alpha) - 1 - 2^{-\alpha} = 1$.

Now suppose that $\beta < \alpha$. Choose a "suitably large" $N$ and a constant $C$ such that $S(n) \geq C n^{\beta}$ for all $n \leq N$. Then it's easy to show that that inequality remains true for all $n$ (in fact it gets better - but this doesn't really matter, since we could just use a slightly larger $\beta$ instead). So in particular $n^\beta = o(S(n))$ for all $\beta < \alpha$. Similarly $S(n) = o(n^{\gamma})$ for all $\gamma > \alpha$.

Now it does seem that in fact $S(n) = C n^{\alpha} (1 + o(1))$ for $C \approx 0.19165$, and I don't quite see how to get that level of detail, but frankly I don't really need it.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ One can indeed prove that $S(x) \sim Cx^{\alpha}$, but since you don't need it I won't bother answering. The idea is to work with the series $\sum_{n=1}^{\infty} s(n)n^{-s}$ which is quite interesting. It looks in a suitable half plane like $F(s)/(2-2^{-s}-\zeta(s))$, and its first singularity is at $s=\alpha$. Then by standard techniques one can work out an asymptotic, but the ideas are a little bit more involved than usual (about the level of the proof of the prime number theorem). $\endgroup$
    – Lucia
    Commented Mar 12, 2014 at 1:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .