top of page
  • Jesse Sakari Hyttinen

Trees and partitions unite - Jesse Hyttinen

Updated: Apr 21, 2021


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! 

4 views0 comments

Recent Posts

See All

The rules of battle 2 - Jesse Hyttinen

Hi and welcome to the Matladpi blog! To use treespeak, one must have at least one aspect granting condition matrix integrated in to his/her mind. No one has a high tsm by just being born, though. It t

How to generate trees - Jesse Hyttinen

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,

Thoughts on my tree theorem - Jesse Hyttinen

Hi and welcome to the Matladpi blog! The theorem that I have discovered quite a while ago about mathematical trees has some pretty interesting consequences. For a remainder, the theorem is stated as t

Post: Blog2_Post
bottom of page