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!

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

The evaluation of your sequence is equivalent to the evaluation of certain weighted sums over binary trees. The resulting identities are often called hook length formulas.

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$.

Now, for those that are curious, such hook length formulas have been investigated for other classes of trees, and there is a unifying Hopf Algebraic perspective behind all such calculations. This is explained in "Tree hook length formulae, Feynman rules and B-series" by B. Jones, K. Yeats.

  • $\begingroup$ Very nice answer! $\endgroup$ Sep 27 '20 at 21:03

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.