# What are these recursively defined sequences called?

Let $$F(x,y)$$ be a function of two variables, defined for all positive integers $$x$$ and $$y$$. Define a sequence $$a_n$$ recursively by setting $$a_1 = 1$$ and $$a_n = \sum_{k=1}^{n-1} F(k, n-k) \cdot a_k a_{n-k}.$$

Is there a common name for such recursively defined sequences? A study for some general classes of $$F$$? I'll probably "show my cards" more in another post, but for now I'd like to search the literature a bit more... unfortunately I can't figure out the right term to search for!

• Isn't this some type of convolution, perhaps? Sep 26 '20 at 21:19
• I might call this a "weighted Catalan recurrence." Sep 26 '20 at 21:49
• @SamHopkins Thanks! That brings up a lot of interesting recurrences... nothing quite like what I want (yet?) but a good lead. Sep 27 '20 at 3:11

Suppose $$\mathcal B_n$$ denotes the set of full binary trees with $$n$$ internal vertices. For some tree $$T\in \mathcal B_n$$ and vertex $$v\in T$$ we define the $$F$$-hook length of $$v$$ to be $$H(v)=F(p+1,q+1)$$ if the left tree below $$v$$ is in $$\mathcal B_p$$ and the right tree below $$v$$ is in $$\mathcal B_{q}$$. The elements of your sequence satisfy $$a_{n}=\sum_{T\in \mathcal B_{n-1}}\prod_{v\in T}H(v).$$
A particularly cool example due to Postnikov is given by the hook function $$F(p,q)=1+\frac{1}{p+q-1}$$ which leads to the strikingly simple $$a_n=n^{n-2}\frac{2^{n-1}}{(n-1)!}.$$ This sparked some curiosity about which functions $$F$$ give rise to simple evaluations for $$a_n$$. You can find more examples in the paper "Hook Length Formulas for Trees by Han's Expansion" by W. Chen, O. Gao, P. Guo but there are more papers out there on the topic.
All the investigated examples that I've seen use hook functions $$F(p,q)$$ that depend only on $$p+q$$. If we think in analogy with hook length formulas for partitions (where the analogue of Postnikov's formula is the Nekrasov-Okounkov formula) this is analogous to hook lengths being a sum $$a+\ell+1$$ where $$a,\ell$$ are the arm and leg of a box. The classical hook length formula, or Nekrasov-Okounkov formula use hook functions that depend only on $$a+\ell$$ but their $$q,t$$ generalizations, as well as the theory of Macdonald polynomials show that there are interesting formulas where the weight for each box depends on $$a$$ and $$\ell$$ separately. This makes me hopeful that the same can happen for trees, so I expect there to be hook length formulas for more general $$F(p,q)$$ that doesn't just depend on $$p+q$$.