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}$?

Improve this question
$\endgroup$
7
  • $\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
    Commented Dec 18, 2017 at 11:18
  • $\begingroup$ What about $f(1)$? $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2017 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
    Commented Dec 18, 2017 at 12:01
  • $\begingroup$ Then do define it for $m>1$. The identity follows by trivial induction on $m$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 18, 2017 at 12:19
  • 1
    $\begingroup$ I will try to expand in an answer $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Dec 18, 2017 at 12:46

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

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