Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ColijnPlazzottaTree

Source Notebook

Generate the rooted binary tree using Colijn–Plazzotta bijection

Contributed by: Shenghui Yang

ResourceFunction["ColijnPlazzottaTree"][n]

generates the rooted binary tree with Colijn-Plazzotta bijection given rank n.

ResourceFunction["ColijnPlazzottaTree"][n,"SubtreeRanks"]

returns the tuple from Colijn-Plazzotta subtrees.

ResourceFunction["ColijnPlazzottaTree"]["Reset"]

clears the memory used for efficiency.

Details

ColijnPlazzottaTree returns a Tree object.
The generated tree is labeled by pre-order depth-first traversal using Colijn-Plazzotta bijection.
Let T be a set of all unlabeled rooted binary trees, then the Colijn-Plazzotta bijection is a function f: T→ ℤ+ that satisfies: a) f(t) if t has one leaf; b) otherwise let l(t) be left subtree of t and r(t) be the right subtree, such that f(l(t))>= f(r(t)). Then we have the recursive definiton of f: f(t) =1/2 · f(l(t)) [f(l(t)) - 1] + 1+ f(r(t)). ColijnPlazzottaTree uses the inverse of the map to create the rooted binary tree given the value of f and labels each node using pre-order depth-first traversal.
The recurrence uses caching to speed up computation and avoid repetitive operation. Use ResourceFunction["ColijnPlazzottaTree"]["Reset"] to clean the memoization and release memory.

Examples

Basic Examples (1) 

Create the Colijn-Plazzotta tree with rank 20:

In[1]:=
ResourceFunction["ColijnPlazzottaTree"][20]
Out[1]=

Scope (1) 

Tabulate the value of f(t) with the paired ranks from subtrees along with the associated binary tree and the number of leaves in each tree:

In[2]:=
ResourceFunction["NiceGrid"][ Table[With[{t = ResourceFunction["ColijnPlazzottaTree"][k]}, {k, ResourceFunction["ColijnPlazzottaTree"][k, "SubtreeRanks"], t, TreeLeafCount[t]}], {k, 6}], {"f(t)", "(f(l(t)),f(r(t)))", "t", "# of leaves"}, ItemSize -> {{4, 11, 6, 8}} ]
Out[2]=

Properties and Relations (3) 

The sequence A357701 on OEIS lists the reading of the depth of each node in Colijn Plazzotta binary tree using pre-order depth first traversal. For instance, using n=6 in the example section on the OEIS page:

In[3]:=
t = ResourceFunction["ColijnPlazzottaTree"][6]
Out[3]=
In[4]:=
cpt = Array[Length[TreePosition[#][t][[1]]] &, 9]
Out[4]=

Retrieve the sequence from OEIS and highlight the matching values:

In[5]:=
ResourceFunction["OEISSequence"][ "A357701"] /. {before___, s : PatternSequence[0, 1, 2, 3, 3, 2, 1, 2, 2], after___} :> {before, Sequence @@ ( Style[#, Red] & /@ {s}), after}
Out[5]=

The number of nodes grows very slowly with n:

In[6]:=
Tree[ResourceFunction["ColijnPlazzottaTree"][10^10], TreeElementLabel -> All -> None]
Out[6]=

Convert the subtree ranks back to the input:

In[7]:=
ResourceFunction["ColijnPlazzottaTree"][5000]
Out[7]=
In[8]:=
p = ResourceFunction["ColijnPlazzottaTree"][5000, "SubtreeRanks"]; {p, 1 + Binomial[100, 2] + 49}
Out[9]=

Possible Issues (1) 

The input of ColijnPlazzottaTree must be a non-negative integer. Otherwise, the function returns unevaluated:

In[10]:=
ResourceFunction["ColijnPlazzottaTree"][-100]
Out[10]=

Neat Examples (3) 

The leaf count for each Colijn-Plazzotta binary tree yields A064064 on OEIS:

In[11]:=
Table[TreeLeafCount[ResourceFunction["ColijnPlazzottaTree"][k]], {k, 30}]
Out[11]=

The sequence has the following recurrence:

In[12]:=
a[0] = 1; a[n_] := With[{s = Floor[(Sqrt[8*n - 7] - 1)/2]}, a[s] + a[n - s*(s + 1)/2 - 1]]; Array[a, 30, 0]
Out[12]=

The dependence of the terms in the above recursive function call:

In[13]:=
callDep[n_] := With[{s = Floor[(Sqrt[8*n - 7] - 1)/2]}, {s -> n, n - s*(s + 1)/2 - 1 -> n}]
In[14]:=
Graph[Flatten[callDep /@ Range[20]] // Union, VertexLabels -> "Name", GraphLayout -> "LayeredDigraphEmbedding"]
Out[14]=

Publisher

Shenghui Yang

Requirements

Wolfram Language 14.0 (January 2024) or above

Version History

  • 1.0.0 – 18 April 2025

Source Metadata

Related Resources

License Information