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
    Dec 18, 2017 at 11:18
  • $\begingroup$ What about $f(1)$? $\endgroup$
    – Emil Jeřábek
    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
    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
    Dec 18, 2017 at 12:19
  • 1
    $\begingroup$ I will try to expand in an answer $\endgroup$
    – მამუკა ჯიბლაძე
    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
    Dec 18, 2017 at 13:00
  • $\begingroup$ The fraction $\frac12$ comes from 'half-catalans' is 'catalan' by 2. $\endgroup$
    – Turbo
    Dec 18, 2017 at 13:00
  • $\begingroup$ $\log(g(n))/\log(\textrm{Catalan}_n)$ seems to be unbounded $\endgroup$
    – მამუკა ჯიბლაძე
    Dec 23, 2017 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.