When generating random binary tree, what's the meaning of empty nodes?

[skywildworld]

According to https://github.com/facebookresearch/SymbolicMathematics/blob/master/src/envs/char_sp.py,

_D[e][n] represents the number of different binary trees with n nodes that can be generated from e empty nodes, using the following recursion: D(0, n) = 0 D(1, n) = Cn (n-th Catalan number) D(e, n) = D(e - 1, n + 1) - D(e - 2, n + 1)

I understand D(1,n) as number of different random binary tree with n node, but what is the meaning of e "empty node" in D(e,n)

[f-charton]

Empty here means unallocated : when generating a tree, you start with one empty (root) node, that can hold a leaf or a binary operator. Because you want the tree to have at least one operator, you build this first node as a binary operator, and now have a partial tree with one operator and two empty nodes. In the first empty node, you can either build a leaf, and then you will have a tree with one operator and one empty node, or an operator, and you will have a tree with 2 operators and 3 empty nodes... By repeating the process, you can build all binary trees.

The generation procedure is described in more details in section C of the appendix of our paper (https://arxiv.org/pdf/1912.01412.pdf)