TreePatterns 1.09

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

TreePatterns is a package for studying trees that avoid a given tree pattern.
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

TreePatterns uses functions from my package BinaryTrees, so you will need to have BinaryTrees installed as well.

To use TreePatterns, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<TreePatterns`

Representing trees

A rooted tree is represented by an expression in which each vertex corresponds to a list containing its children. For example, here is a 5-leaf binary tree:

{{{},{}},{{{},{}},{}}}

The Wolfram Language symbol TreeForm displays expressions graphically.
BareTreeForm uses TreeForm to draw trees without vertex labels:

BareTreeForm[{{{},{}},{{{},{}},{}}}]

BinaryTrees gives a list of all binary trees with a fixed number of leaves.

BinaryTrees[4]
BareTreeForm/@%

Tree patterns and specific bijections

Pattern matching functionality in the Wolfram Language provides a convenient way to compute (by exhaustive search) how many binary trees do not contain another binary tree as a contiguous subtree.

First we need to render a tree as a pattern.

BinaryTrees[4][[-1]]

TreePattern[{{{{},{}},{}},{}}]

Now we can use this pattern in, for example, FreeQ.
For the particular tree, we get the sequence of Motzkin numbers.

Table[Length[Select[BinaryTrees[n],Function[binarytree,FreeQ[binarytree,{{{{___},{___}},{___}},{___}}]]]],{n,10}]

BinaryTree45Bijection is an explicit bijection between binary trees avoiding {{{{___},{___}},{___}},{___}} and Motzkin paths.
(The name comes from this tree being indexed as the fifth binary tree on 4 leaves.)

BinaryTree45Bijection/@Select[BinaryTrees[5],Function[binarytree,FreeQ[binarytree,{{{{___},{___}},{___}},{___}}]]]

The inverse is BinaryTree45BijectionInverse.

BareTreeForm/@BinaryTree45BijectionInverse/@%

Computing the number of binary trees avoiding a given pattern

One way to more efficiently determine the number of binary trees avoiding a given tree pattern t is to first compute the generating function counting n-vertex binary trees avoiding t, which is always algebraic, and then extract the desired coefficient. AvoidingWeightEquation gives a polynomial equation that the generating function satisfies.

AvoidingWeightEquation[{{{{},{}},{}},{}},f,x]

The function SeriesSolve in my IntegerSequences package gives the explicit coefficients of f.

Needs["IntegerSequences`"]
SeriesSolve[x-f[x]+(x^2) f[x]+(x^3) ((f[x])^2)==0,f[x],{x,0,20}]

More generally, WeightEquation computes a polynomial equation satisfied by the generating function counting all binary trees with respect to multiple tree patterns.

WeightEquation[{{},{{},{}}},{{{{},{}},{}},{}},f,x]

%/.{x[{}]->x,x[{{},{{},{}}}]->y,x[{{{{},{}},{}},{}}]->z}

Equivalence of tree patterns and general bijections

Two tree patterns s and t are equivalent if for all n the number of n-leaf binary trees avoiding s is the same as the number of n-leaf binary trees avoiding t. One can determine equivalence simply by computing the polynomial equations satisfied by the generating functions corresponding to the two tree patterns.

BinaryTreeClassData contains precomputed data about the equivalence classes of binary trees. It works much like one of the standard Mathematica data paclets (GraphData, PolyhedronData, etc.).

BinaryTreeClassData["Properties"]

There are three equivalence classes of 5-leaf binary trees:

BinaryTreeClassData[5]

Here are the members of those equivalence classes:

BareTreeForm/@BinaryTreeClassData[{5,1},"Members"]

BareTreeForm/@BinaryTreeClassData[{5,2},"Members"]

BareTreeForm/@BinaryTreeClassData[{5,3},"Members"]

BareTreeForm/@BinaryTrees[5]

Given two equivalent tree patterns, one would like an explicit bijection between the respective sets of n-leaf trees avoiding them. Often a bijection can be accomplished by a top-down or bottom-up replacement of one leaf pattern by the other.

Such a replacement is determined by the permutation of leaves. ProbableAvoidingBijections finds permutations that produce bijections under the assumption that several overlapped patterns never break the bijection.

ProbableAvoidingBijections[BinaryTrees[5][[2]],BinaryTrees[5][[3]]]

TreeReplacementRules turns the permutation into explicit rules, and TopDownReplaceAll performs the top-down replacement.

rules=TreeReplacementRules[BinaryTrees[5][[2]],BinaryTrees[5][[3]],{1,3,4,2,5}]

Applying the top-down replacement to a tree avoiding the first pattern produces a tree that avoids the second pattern:

And@@(FreeQ[TopDownReplaceAll[#1,rules],TreePattern[BinaryTrees[5][[3]]]]&)/@Select[BinaryTrees[7],FreeQ[#1,TreePattern[BinaryTrees[5][[2]]]]&]

Clear[rules]

For the nontrivial equivalence class of 5-leaf binary trees, the following graph shows which tree patterns can be proven equivalent by a top-down replacement (solid blue edges) and which patterns are equivalent by left–right reflection (dashed gray edges). However, a bug in Graph styles edges incorrectly when there are multiple edges from one vertex to another; for example, of the four edges between vertices 3 and 12 here, two should be blue:

BinaryTreeClassData[{5,2},"EquivalenceGraph"]

This is what was produced in a previous version, before GraphPlot changed and EdgeRenderingFunction was deprecated:

BinaryTreeClassData[{5,2},"EquivalenceGraphImage"]

Package symbols

Bijections

?Bijections

For each pair of 4-leaf binary trees, compute the permutations that induce top-down replacement bijections:

Grid[Outer[If[#1≠#2,Column[Bijections[##1]]]&,BinaryTrees[4],BinaryTrees[4],1]]

BinaryTree42Bijection and BinaryTree42BijectionInverse

?BinaryTree42Bijection

BinaryTree42Bijection/@Select[BinaryTrees[5],Function[binarytree,FreeQ[binarytree,TreePattern[BinaryTrees[4][[2]]]]]]

?BinaryTree42BijectionInverse

BareTreeForm/@BinaryTree42BijectionInverse/@{{1,1,1},{1,1,0},{1,0,1},{1,0,0},{0,1,1},{0,1,0},{0,0,1},{0,0,0}}

BinaryTree43Bijection and BinaryTree43BijectionInverse

?BinaryTree43Bijection

BinaryTree43Bijection/@Select[BinaryTrees[5],Function[binarytree,FreeQ[binarytree,TreePattern[BinaryTrees[4][[3]]]]]]

?BinaryTree43BijectionInverse

BareTreeForm/@BinaryTree43BijectionInverse/@{{1,1,1},{1,1,0},{1,0,1},{1,0,0},{0,1,1},{0,1,0},{0,0,1},{0,0,0}}

BinaryTree45Bijection and BinaryTree45BijectionInverse

?BinaryTree45Bijection

BinaryTree45Bijection/@Select[BinaryTrees[5],Function[binarytree,FreeQ[binarytree,TreePattern[BinaryTrees[4][[5]]]]]]

?BinaryTree45BijectionInverse

BareTreeForm/@BinaryTree45BijectionInverse/@{{0,0,0,0},{0,0,1,-1},{0,1,-1,0},{0,1,0,-1},{1,-1,0,0},{1,-1,1,-1},{1,0,-1,0},{1,0,0,-1},{1,1,-1,-1}}

BinaryTreeClassData

?BinaryTreeClassData

Display the equivalence classes of 6-leaf binary trees:

(BareTreeForm/@BinaryTreeClassData[#1,"Members"]&)/@BinaryTreeClassData[6]

Compute the polynomial equation satisfied by the generating function for binary trees with respect to number of vertices and number of instances of a given tree from class 6.3:

BinaryTreeClassData[{6,3},"WeightEquation"][f[x,y],x,y]

Compute the number of equivalence classes of n-leaf binary trees for 1≤n≤8:

Length/@BinaryTreeClassData/@Range[8]

BinaryTreePatternQ

?BinaryTreePatternQ

BinaryTreePatternQ[{{___},{___}}]

BinaryTreePatternQ[{{___},{___},{___}}]

BottomUpReplaceAll and TopDownReplaceAll

?BottomUpReplaceAll

rule={$1_,{$2_,{{$3_,$4_},$5_}}}:>{$1,{{$3,$4},{$2,$5}}};
tree={{},{{},{{},{{{},{{{},{{},{}}},{}}},{{},{}}}}}};
BareTreeForm[tree]

BareTreeForm[BottomUpReplaceAll[tree,rule]]

?TopDownReplaceAll

BareTreeForm[TopDownReplaceAll[tree,rule]]

Clear[rule,tree]

FindOverlaps

?FindOverlaps

tree1=BinaryTrees[4][[2]];
tree2=BinaryTrees[4][[3]];
BareTreeForm/@{tree1,tree2}

FindOverlaps[TreePattern[tree1],TreePattern[tree2]]

?Leaves

FindOverlaps[TreePattern[tree1],TreePattern[tree2],Leaves->True]

Clear[tree1,tree2]

MatchingTrees and NonMatchingTrees

?MatchingTrees

MatchingTrees[TreePattern[BinaryTrees[4][[1]]]]

?NonMatchingTrees

NonMatchingTrees[TreePattern[BinaryTrees[4][[1]]]]
BareTreeForm/@%

PatternIntersection

?PatternIntersection

tree1=BinaryTrees[4][[2]];
tree2=BinaryTrees[4][[3]];
BareTreeForm/@{tree1,tree2}

PatternIntersection[TreePattern[tree1],TreePattern[tree2]]
BareTreeForm[%]

Clear[tree1,tree2]

ProbableAvoidingBijectionQ

?ProbableAvoidingBijectionQ

ProbableAvoidingBijectionQ[TreePattern[BinaryTrees[4][[2]]],TreePattern[BinaryTrees[4][[3]]],{{$2_,$3_},{$1_,$4_}}:>{$1,{{$2,$3},$4}}]

ProbableAvoidingBijectionQ[TreePattern[BinaryTrees[4][[2]]],TreePattern[BinaryTrees[4][[3]]],{$1_,{{$2_,$3_},$4_}}:>{{$2,$3},{$1,$4}}]

ProbableAvoidingBijections

?ProbableAvoidingBijections

ProbableAvoidingBijections[BinaryTrees[4][[2]],BinaryTrees[4][[3]]]

TreePattern and FromTreePattern

?TreePattern

TreePattern[BinaryTrees[5][[5]]]

?FromTreePattern

FromTreePattern[{{___},{{{{___},{___}},{___}},{___}}}]

TreeReplacementRules

?TreeReplacementRules

TreeReplacementRules[BinaryTrees[4][[1]],BinaryTrees[4][[2]],{1,3,2,4}]

Weight

?Weight

BareTreeForm[BinaryTrees[5][[10]]]
Weight[BinaryTrees[5][[10]],{{},{}},x]

Weight[BinaryTrees[5][[10]],{{},{{},{}},{{},{{},{}}}},{x,y,z}]

WeightEquation and AvoidingWeightEquation

?AvoidingWeightEquation

The five binary trees with 4 leaves and polynomial equations satisfied by the generating function counting binary trees that avoid each:

Grid[({BareTreeForm[#1],AvoidingWeightEquation[#1,f,x]}&)/@BinaryTrees[4]]

?WeightEquation

More generally, we can count all binary trees with respect to number of vertices and number of occurrences of a given 4-leaf pattern:
Setting y=0 gives the equations satisfied by the avoiding generating function.

Grid[({BareTreeForm[#1],WeightEquation[#1,f,x]/.{x[{}]->x,x[#1]->y}}&)/@BinaryTrees[4]]