Hi and welcome to the Matladpi blog!
As you may already know, trees can be expressed as integer partitions. To construct a tree as a partition, you have to know several rules:
Every vertex is expressed in the partition as the number one (1)
Edges connecting vertices and branches to each other are expressed as addition signs (+)
The vertex that is the starting point in a tree is the first number one in the partition
In a rooted tree, the first number one in the partition is the root
A branch (size > 1) can be expressed as a number m, if the branch is the following structure: there are m - 1 external vertices which are connected to one internal vertex
Vertices have a size of 1; an empty branch has a size of 0 and is expressed as the number zero (0)
The empty branch does not change the graphical structure of a tree or the resulting partition (For example, 1 + 2 + 0 = 1 + 2)
A branch (size > 2) other than those that can be expressed as single numbers, must be expressed with brackets. The starting bracket ' ( ' starts the branch and the ending bracket ' ) ' ends it. The internal vertex starting the branch is expressed as the first number one inside the brackets.
Branch (number) m = (1 + 1*(m - 1))
Multiplication sign (*) is used to compactify a group of identical branches/ external vertices into a notation p*q, where p is the expression of the branch/ external vertex and q is the quantity factor
Inside the brackets, a branch/ external vertex is connected by an edge (+) to the internal vertex (1) of that branch. Likewise, outside of any brackets, the branch/ external vertex is connected by an edge (+) to the starting vertex (1) of that tree.
External vertices are the last numbers and number ones inside the partition and brackets
The ordering of the branches connected to a root/ internal/ starting vertex inside the partition does not matter. However, the partition must start with a number one, any brackets must have a number one as the starting structure, and all other number ones must be the last numbers inside brackets and the partition.
For example, 1 + 2 + 3 = 1 + 3 + 2, 1 + (1 + 2)*4 + 2*3 = 1 + 2*3 + (1 + 2)*4
Examples:
Tree: There is a starting vertex that is connected to two external vertices and one internal vertex. The internal vertex is connected to another external vertex.
Partition: 1 + (1 + 1) + 1*2
Another version: 1 + 2 + 1*2
Tree: There is a root vertex that is connected to eleven external vertices.
Partition: 1 + 1*11
Tree: There is a starting vertex that is connected to three internal vertices. The first internal vertex is connected to two external vertices. The second internal vertex is connected to one external vertex and the third internal vertex is connected to one external vertex and yet another internal vertex, which in turn is connected to an external vertex.
Partition: 1+(1+1*2)+(1+1)+(1+(1+1)+1)
Another version: 1+3+2+(1+(1+1)+1)
Another version: 1+2+(1+(1+1)+1)+3
Tree: There is a single root.
Partition: 1
Tree: There is a starting point that is connected to an internal vertex. The internal vertex is in turn connected to an empty branch.
Partition: 1 + (1 + 0)
Another version: 1 + 1
Note: In the last example the internal vertex is actually an external vertex, as 1 + (1 + 0) = 1 + 1
I am Jesse Sakari Hyttinen and I will see you in the next post!