2
$\begingroup$

Denote when $k>2m$ $$f_k(2m)=\sum_{i=1,i\geq1}^m\binom{2m}{i}f_k(i)f_k(2m-i)$$ $$f_k(2m+1)=\sum_{i=1,i\geq1}^m\binom{2m+1}{i}f_k(i)f_k(2m+1-i)$$

$$f_k(0)=1.$$ $$f_k(1)=k.$$

  1. What is a good bound for $f_{2^{n+1}}(2^{n})$?

  2. How does it compare with $\binom{2^{n+1}}{2^n}$? Is $f_{2^{n+1}}(2^{n})>\binom{2^{n+1}}{2^n}$?

$\endgroup$
  • $\begingroup$ Your rules do not seem to work properly. They start with $f(0)=f(0)$, then $f(1)=f(0)f(1)$, then $f(2)=f(0)f(2)+2f(1)^2$, which does not determine $f(0)$, $f(1)$ and $f(2)$. Probably your equations should be adjusted slightly. $\endgroup$ – Neil Strickland Dec 18 '17 at 11:18
  • $\begingroup$ What about $f(1)$? $\endgroup$ – Emil Jeřábek Dec 18 '17 at 11:49
  • 1
    $\begingroup$ So now, $f(k,m)=k^mf(1,m)$, hence $f(2^{n+1},2^n)\ge2^{(n+1)2^n}\ge2^{2^{n+1}}>\binom{2^{n+1}}{2^n}$. $\endgroup$ – Emil Jeřábek Dec 18 '17 at 12:01
  • $\begingroup$ Then do define it for $m>1$. The identity follows by trivial induction on $m$. $\endgroup$ – Emil Jeřábek Dec 18 '17 at 12:19
  • 1
    $\begingroup$ I will try to expand in an answer $\endgroup$ – მამუკა ჯიბლაძე Dec 18 '17 at 12:46
8
$\begingroup$

For brevity, rewrite the recursion as$$f_k(n)=\sum_{1\leqslant i\leqslant\frac n2}\binom nif_k(i)f_k(n-i).$$Now divide it by $n!k^n$ and rewrite like this:$$\frac{f_k(n)}{n!k^n}=\frac1{n!}\sum_{1\leqslant i\leqslant\frac n2}\binom nii!(n-i)!\frac{f_k(i)}{i!k^i}\frac{f_k(n-i)}{(n-i)!k^{n-i}}.$$ It follows that for$$g_k(n):=\frac{f_k(n)}{n!k^n}$$we get$$g_k(n)=\sum_{1\leqslant i\leqslant\frac n2}g_k(i)g_k(n-i),$$and $g_k(1)=1$ (in particular $g_k(n)$ does not depend on $k$).

This is the recursion for A000992 (number of (unlabeled, rooted) ordered trees on $n-1$ vertices in which all outdegrees are $\leqslant2$ and, for each vertex of outdegree $2$, the sizes of its two subtrees are weakly increasing left to right ($n\geqslant2$)). That page contains some information about these numbers.

$\endgroup$
  • $\begingroup$ So the growth of $g_k(n)$ is $\frac{1}{2(n+1)}\binom{2n}{n}$? $\endgroup$ – Brout Dec 18 '17 at 13:00
  • $\begingroup$ The fraction $\frac12$ comes from 'half-catalans' is 'catalan' by 2. $\endgroup$ – Brout Dec 18 '17 at 13:00
  • $\begingroup$ $\log(g(n))/\log(\textrm{Catalan}_n)$ seems to be unbounded $\endgroup$ – მამუკა ჯიბლაძე Dec 23 '17 at 9:12

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.