Hi and welcome to the Matladpi blog!

Tree generation is like listing all the partitions of a given number, but with a few differences. For example, if we listed all the partitions of the number five, this would be quite equal to generating the basic forms of rooted trees with a size of six.

What is different, however, is that in rooted tree generation, we continue listing partitions of numbers inside the original partitions. And this listing inside a partition involves setting number one as an internal vertex starting the branch, just as we set the root vertex in the whole tree, in other words the first number one in the partition.

Here is an example:

5 = 1+1*4 = 1+2+1*2 = 1+3+1 = 1+4

= 1+2*2

These are the basic forms - the forms we can express without brackets - of rooted trees with a size of five. Notice how the first number is always one: this number is actually expressing the root. We can then think that the basic forms of rooted trees with size m are equivalent in a combinatorial sense to all the partitions of an integer m - 1.

If the advanced forms - the forms with mandatory brackets - are added, the result would look like this:

5 = 1+1*4 = 1+2+1*2 = 1+3+1

= 1+2*2 = 1+(1+2)+1

= 1+4

= 1+(1+2+1)

= 1+(1+3)

= 1+(1+(1+2))

Notice that 3 = (1+1*2) and 4 = (1+1*3), so the process can be interpreted as iteration of listing partitions.

I am Jesse Sakari Hyttinen and I will see you in the next post!