What is the TREE sequence?
The TREE function describes the maximum length of a special sequence of finite rooted trees. Each tree has vertices carrying labels selected from a fixed set of available labels.
The sequence must obey two rules: the tree at position i can contain at most i vertices, and no earlier tree may embed into a later tree while preserving the labels.
The trees use n available labels and satisfy the size restriction at every position.
TREE value explorer
Select a small number of available labels to explore its known TREE value. This explorer shows exact small values and a symbolic result for TREE(3).
The three-label case produces an extraordinarily large finite number.
TREE(3) is a precisely defined finite integer. Its growth is so extreme that ordinary numerical calculation and decimal expansion are not practical.
Known small TREE values
| Function | Value | Interpretation |
|---|---|---|
| TREE(1) | 1 | Only one tree can appear in a bad sequence. |
| TREE(2) | 3 | The exact maximum length for two labels. |
| TREE(3) | Symbolic | A finite number vastly larger than Graham's number. |
These values use the standard TREE function convention described on this page.
How is a TREE sequence constructed?
A sequence is built by choosing a finite rooted tree at each position. The number of vertices is limited by the position, and the labels must come from the selected set.
Step 1: Choose labels
For TREE(2), two labels are available.
Step 2: Build a tree
Choose a finite rooted tree and label its vertices.
Step 3: Check embeddings
An earlier tree must not embed into a later one.
These diagrams are conceptual illustrations of labeled rooted trees. They are not presented as a specific optimal bad sequence.
The rules of a bad tree sequence
1Finite rooted trees
Every term is a finite rooted tree. A rooted tree has a designated root vertex, with its other vertices arranged in a branching structure.
2Limited tree size
The tree at position i may have at most i vertices. Thus the first tree has at most one vertex, the second at most two, and so on.
The number of vertices in tree Ti cannot exceed i.
3Label preservation
Each vertex receives one of n possible labels. An embedding must preserve the labels of the vertices it maps.
4No earlier tree embeds into a later tree
For every pair of positions i and j with i less than j, Ti must not embed into Tj. This is what makes the sequence a bad sequence.
What does tree embedding mean?
An embedding is a way of finding one tree inside another while respecting the tree structure and the vertex labels. The TREE function uses label-preserving homeomorphic embedding.
Informally, branches may be represented by longer paths in the larger tree, but the relevant branching relationships and labels must be preserved. The exact mathematical definition is more precise than simple visual containment.
No earlier tree may embed into any later tree.
Why is TREE(n) always finite?
At first, the rules might appear to allow a sequence to continue forever. However, a fundamental result in combinatorics called Kruskal's tree theorem rules this out.
The theorem establishes a well-quasi-ordering property for finite labeled trees under the relevant embedding relation. In particular, every infinite sequence of such trees contains an earlier tree that embeds into a later one.
An infinite bad sequence is therefore impossible. Since the size restriction also gives only finitely many possible trees at each position, the maximum length TREE(n) is finite.
Every fixed finite number of available labels gives a finite TREE value.
Why is TREE(3) so enormous?
The transition from two labels to three labels changes the possible structures and the lengths of bad sequences dramatically. The third label permits much more elaborate arrangements of trees.
The result is a number so large that Graham's number is tiny by comparison. TREE(3) is often used in discussions of extreme finite numbers because it arises from a precise mathematical theorem rather than an arbitrary large-number naming convention.
This comparison is about mathematical magnitude, not a decimal calculation.
TREE sequence versus other large-number functions
TREE(3) is different from numbers defined by exponentiation, tetration, or hyperoperations. It comes from a combinatorial maximum-length problem.
| Function or number | Mathematical source | How it is defined |
|---|---|---|
| Graham's number | Ramsey theory | Recursive Knuth up-arrow sequence |
| TREE(n) | Combinatorics and mathematical logic | Maximum length of a bad sequence of labeled trees |
| Ackermann function | Computability theory | Nested recursive function |
| Fast-growing hierarchy | Proof theory | Functions indexed by ordinal levels |
| Busy Beaver function | Computability theory | Maximum behavior of halting Turing machines |
Frequently asked questions
What is the TREE sequence?
The TREE sequence is a sequence of extremely large finite integers from mathematical logic and combinatorics. TREE(n) describes the maximum length of a certain kind of bad sequence of finite rooted trees labeled using n available labels.
What is TREE(1)?
TREE(1) = 1. With only one label, a one-vertex tree embeds into every later nonempty tree, so a bad sequence cannot have a second term.
What is TREE(2)?
TREE(2) = 3. This is the exact value under the standard TREE function definition used by this explorer.
What is TREE(3)?
TREE(3) is a finite integer of extraordinary size. It is famous because it is vastly larger than Graham’s number.
What is a bad sequence of trees?
It is a sequence in which no earlier tree can be embedded into any later tree while preserving the labels. The size of the tree at position i is restricted to at most i vertices.
What does tree embedding mean?
A tree embedding maps vertices of one tree into another in a way that preserves the relevant tree structure and labels. The standard TREE function uses label-preserving homeomorphic embedding.
Why is TREE(n) finite?
Kruskal’s tree theorem implies that finite labeled trees are well-quasi-ordered under the relevant embedding relation. Consequently, an infinite bad sequence cannot exist, and the size-restricted maximum length is finite.
Can this calculator calculate TREE(3)?
No ordinary calculator can expand TREE(3) into a decimal integer. This page is a mathematical explorer: it displays known small values and explains the exact recursive combinatorial definition.
Is TREE(3) larger than Graham’s number?
Yes. TREE(3) is vastly larger than Graham’s number. The two numbers arise from different mathematical constructions.
Is TREE(3) infinite?
No. TREE(3) is finite. Its enormous size does not make it infinite.
Explore more large-number tools
Continue exploring large numbers, recursive functions, and mathematical growth systems.