++ed by:

1 non-PAUSE user.

and 1 contributors

NAME

Graph::Maker::Catalans - create Tamari lattice and other Catalan object graphs

SYNOPSIS

`````` use Graph::Maker::Catalans;
\$graph = Graph::Maker->new ('Catalans', N => 4);``````

DESCRIPTION

`Graph::Maker::Catalans` creates `Graph.pm` graphs where each vertex represents a "Catalan object", meaning one of

``````    balanced binary (Dyck word) of length 2N
binary tree of N internal vertices
ordered forest of N vertices

num vertices = Catalan(N) = 1,1,2,5,14,42, ... (A000108)``````

Binary trees are rooted and each vertex has a left and right child subtree, each possibly empty. There are many combinatorial objects enumerated by the Catalan numbers and in one-to-one correspondence. The present ones are where the graph relations here have direct interpretation.

The default graph is the Tamari lattice (associahedron, binary tree rotation graph, see "Rotate" below), with vertex names as balanced binary strings. But there are 12 relation types (10 up to isomorphism) and 11 vertex name types.

Vertex Names

Option `vertex_name_type` chooses the vertex name style. The edge relation rules are sometimes simpler or more complex in one or other type. In all cases the underlying object and relation is unchanged, just the vertex names differ.

Balanced Binary

The default `vertex_name_type => 'balanced'` is strings of N many 1s and N many 0s where the 1s and 0s nest like open and close parens.

``````        /\
/\/  \  /\       mountain range, 1 up, 0 down
/      \/  \
110110001100      balanced binary
(()(()))(())        parens``````

The heights in the mountain range are like nesting levels of the parens. Balanced binary corresponds to a binary tree coded recursively, starting at the root,

``    1, left subtree, 0, right subtree         = balanced``

This is pre-order traversal of the binary tree with 1 for a vertex, 0 for an empty child position (an "external"), and final 0 omitted.

``````               1                    binary tree, pre-order
/       \                1 = "internal" vertex
1             1             0 = "external" empty position
/   \         /   \           last external omitted
0      1      1     (0)
/ \    / \                110110001100
1   0  0   0
/ \
0   0``````

Option `vertex_name_type => 'balanced_postorder'` is the tree coded by postorder traversal. Each external is a 1, each internal is a 0, except the very first 1 omitted. This is a recursive coding

``    left subtree, 1, right subtree, 0     = balanced_postorder``

There is no in-order bit coding because left,1,right is merely 0101010 for every tree.

Depths

Option `vertex_name_type => 'Ldepths'` is left depth of each vertex in pre-order. Left depth is how many left steps down to the vertex. The example above is

``    0,1,1,2,0,1         Ldepths``

In terms of balanced binary, Ldepths is at each 1-bit how many unclosed 1s precede there (excess of 1s over 0s). This is since each 1 is a vertex and the next edge is a left descent, and each 0 goes back up that left (and takes a right descent).

``````    1 101 1 0001 100    balanced binary
0,1,1,2,   0,1      Ldepths``````

Ordered forests are one-to-one with binary trees by the "natural correspondence". (See for example Knuth volume 1 section 2.3.2 for pictures and description.) Ldepths is vertex depth in the ordered forest.

``````    binary left child  = ordered first child       \    natural
binary right child = ordered next sibling      / correspondence

1                1       5
/     \             | \     |           pre-order
2       5            2  3    6           labelling
\     /                |
3   6                 4
/
4

binary tree         ordered forest``````

Option `vertex_name_type => 'Ldepths_inorder'` is the same Ldepths but vertices taken in-order. In terms of balanced binary, this is at each 0 how many unclosed 0s are after it. Or equivalently, how many unclosed 1s precede, with the 0 itself included as a closing.

In terms of ordered forest, in-order binary tree traversal is postorder forest traversal. So `Ldepths_inorder` is forest depths postorder.

Option `vertex_name_type => 'Rdepths_inorder'` is right depths of the binary tree traversed in-order. Right depth is how many right steps down. This is the "distance" representation by Makinen. In terms of ordered forest, right depth is a horizontal position (how many preceding siblings, plus parent how many preceding siblings, etc).

Option `Bdepths_inorder` is all steps down, so `Ldepths_inorder` plus `Rdepths_inorder`.

Option `vertex_name_type => 'Rdepths_postorder'` is right depths of the binary tree traversed post-order.

The above are only one pre and one post. The omitted pre R,B and post L,B do not uniquely identify their tree object, ie. multiple trees have the same resulting vector.

Vpar

Option `vertex_name_type => 'vpar'` gives vertex parent array of the ordered forest in pre-order. Vertices are numbered 1 to N and each vpar entry is the parent vertex number, or 0 if no parent (a root). The first vertex is the first root, so vpar always starts with 0.

``````    1       5
| \     |           vpar
2  3    6         0,1,1,3,0,5
|
4``````

Comparing forests lexicographically by `vpar` is the same as comparing lexicographically by `Ldepths`. So when one of the edge relations is a lex increase of `Ldepths` it is also a lex increase of `vpar` (though the values in the arrays are not the same in general).

Option `vertex_name_type => 'vpar_postorder'` is vertex parent array with forest vertices labelled in post-order. The last vertex is the last root, so `vpar_postorder` always ends with 0.

``````    4       6
| \     |        vpar_postorder
1  3    5         4,3,4,0,6,0
|
2``````

Weights

Option `vertex_name_type => 'Lweights'` gives a list of subtree sizes. This is the of binary tree weights vector considered by Pallo ("Enumerating" below).

Each binary tree external vertex (left to right) is right-most of a sub-tree (the subtree to its left). The top of that sub-tree is found by going up until reaching a vertex (internal or external) which is a left child. The weight is the number of externals at and below there. An external which is already a left child is weight 1 (itself only). The first external is always a left child so Lweights start with 1. The last external is omitted (it would always be N+1).

``````              1
/       \              Lweights
2            5           1,1,2,3, 1,2   (omit e7)
/ \          / \
e1   3        6   e7         Rweights
/ \      / \            3,1,1, 3,1,1   (omit e1)
4   e4  e5   e6
/ \
e2   e3``````

Option `vertex_name_type => 'Rweights'` is similar. Each external vertex is left-most of a subtree (the subtree to its right). The top is by going up until a right child vertex. The last external is always a right child so Rweights end with 1. The first external is omitted (it would always be N+1).

An equivalent definition is to take the internal vertices in-order and Lweight is the size of that vertex plus its left subtree (if any). Or Rweight is itself plus right subtree.

In terms of ordered forests, Lweight is the subtree size at and below each vertex in post-order (since binary tree in-order is forest post-order).

Comma

Option `comma => "string"` is the separator between quantities in the vertex names. The default is empty "" for balanced binary or "," comma for the others.

Terms are single digits for weights and vpar N < 10 and depths N <= 10. Omitting the comma by `comma => ""` is then unambiguous and might be preferred for compact viewing. N=10 ambiguity would be at Catalan(10) = 16796 many vertices which is big but possible.

Rotate

The default `rel_type => 'rotate'` is the Tamari lattice, conceived by Tamari as parenthesizations of N+1 objects and stepped by one application of the associative law, and hence also called an associahedron.

Dov Tamari, "The Algebra of Bracketings and Their Enumeration", Nieuw Archief voor Wiskunde, Series 3, volume 10, 1962, pages 131-146.

``````         -------> 110010 -------_
/                        v              N => 3
101010                      111000          rel_type => "rotate"
\                        ^
--> 101100 --> 110100 -/``````

In terms of binary trees, this is one "rotation", and hence also called a binary rotation graph (eg. Pallo). Rotation is the rearrangement commonly used for rebalancing a binary tree. (Or applying an associative law to operators in an expression parse tree.)

``````         x    (leftward)    y
/ \      -->       / \            binary tree "rotation",
A   y              x   C          edge between vertices x,y
/ \            / \           A,B,C subtrees (possibly empty)
B   C          A   B

1 A 0 1 B 0 C     1 1 A 0 B 0 C     A,B,C balanced substrings
^^^^^             ^^^^^              (possibly empty)``````

A right edge x-y can rotate to left, or a left edge can come from a right rotate, hence the graph is regular of degree N-1.

``````    num edges = (N-1)/2*Catalan(N) or 0 if N=0
= binomial(2N-1, N-2)
= 0,0,1,5,21,84, ... (A002054)
degree N-1 regular (in-degree + out-degree)``````

In terms of balanced binary, rotation moves a 1 to before the shortest non-empty balanced substring immediately preceding,

``````    edge from    1aaaa0 1        where 1aaaa0 shortest balanced
to     1 1aaaa0``````

Moving the 1 has the effect of shifting the 1A0 part up and right,

``````   from      /\          to    /\  /\
/\  /  \   -->        /  \/  \
/\/  \/    \          /\/        \
101100111000          101110011000
****1                 1****``````

Each 01 rotates as in the "from" above, so number of successors is number of 01 pairs. Each 11 as in the "to" above can come from a rotate, so number of predecessors is number of 11 pairs.

In terms of ordered forest, rotation is a vertex move down to deeper level. A vertex y with preceding sibling x has that x drop down to become child of y. y's other children B and further siblings C remain.

``````          x ... y ... further-C                   y ... further-C
|     |                 (leftwards)     |
subtree-A  further-B             -->          x ... further-B
|
subtree-A``````

In terms of `Lweights`, Pallo shows a rotate is one entry increasing by its smallest possible amount, which is adding the size of its immediately preceding sibling (drops to become first child). This is y gaining subtree size x under it. The post-order sequence is unchanged. Pallo reaches the same as Tamari that the result is a lattice.

J. M. Pallo, "Enumerating, Ranking and Unranking Binary Trees", The Computer Journal, volume 29, number 2, 1986, pages 171-175.

Taking `Lweights` as coordinates allows the graph to be drawn as an N-1 dimensional rectangular figure. The first Lweights entry is always 1 so can be ignored as a coordinate. Each edge is then forward along one axis. For N=4 in 3 dimensions the effect is good, but more, in 2D projection at least, tends to become too busy to see much. Geyer draws some in this style.

The undirected graph has a Hamiltonian path per Joan Lucas (simplified by Lucas, van Baronaigien, and Ruskey). And it has a Hamiltonian cycle per Wu and Wang (whose argument can be simplified by expanding as for a path and doing one zig-zag if Catalan(N-1) is odd).

The various `rotate_...` relation types below restrict to just some rotates so are edge subsets of full `rotate`.

Rotate Right or Left Arm

Option `rel_type => 'rotate_rightarm'` restricts to rotates of edges on the right arm of the binary tree, in the manner of

J. M. Pallo, "Right-Arm Rotation Distance Between Binary Trees", Information Processing Letters, volume 87, number 4, 2003, pages 173-177.

``````         -------> 110010 -------_
/                        v         N => 3
101010                      111000     rel_type => "rotate_rightarm"
\
--> 101100 --> 110100``````

The resulting graph is "graded" in that it starts from all edges right arm (101010), and each step reduces them by 1. Counts of trees by right arm length are a row of the Catalan triangle.

``````     T              rotate_rightarm
/ \
*            only rotate edges
/ \           on the right-most arm
*          extending down
/ \``````

In terms of balanced binary, right arm means rotate at "1aaaa0 1" where the 0 there is a return to the zero line. The graph endpoints (`\$graph->successorless_vertices`) have no such returns to zero. They are "1 balanced(N-1) 0", and hence Catalan(N-1) many.

In terms of `Ldepths`, right arm vertices have Ldepth=0 and the x,y vertices of the rotate are consecutive Ldepth=0 (and other non-zeros in between). The rotate increases the depth of the second.

Csar, Sengupta, and Suksompong get various rightarm results too, as "comb poset" of bracketings.

Option `rel_type => 'rotate_leftarm'` restricts to rotates which put a new edge on the left arm, so rotate a right edge of a left arm vertex. This is isomorphic to `rotate_rightarm` by considering binary trees in mirror image. In terms of balanced binary, left arm is a rotate at

``````    11..11 1aaaa0 1 ...          rotate_leftarm
^
start of string initial run of 1s``````

The 1 of 1aaaa0 must be in the run of 1s at the start of the string. It can be anywhere in the run (including the very start of string), with aaaa containing the rest of those 1s.

Rotate First or Last

Option `rel_type => 'rotate_first'` restricts to rotate only at the first possible place. This result is a tree ("leftmost") per,

J. M. Pallo, "Rotational Tree Structures on Binary Trees and Triangulations", Acta Cybernetica, volume 17, 2006, pages 799-810.

``````         -------> 110010 -------_
/                        v         N => 3
101010                      111000     rel_type => "rotate_first"
^
101100 --> 110100 -/``````

Per Pallo, the resulting tree is "graded" by how many balanced binary initial 1s (the left arm vertices). Each first rotate moves the first non-initial-1 to become part of the initial 1s. The start vertices (predecessorless) have 1 initial 1 and steps take them to N 1s at the end (successorless).

The number of vertices at each distance from the end is the Catalan triangle. The predecessorless are Catalan(N-1) which is the end of the triangle row.

Option `rel_type => 'rotate_last'` rotates at the last possible place only. The result is a tree ("rightmost") again per Pallo (above).

``````                  110010 -------_
v         N => 3
101010                      111000     rel_type => "rotate_last"
\                        ^
--> 101100 --> 110100 -/``````

Rotate Empty

Option `rel_type => 'rotate_Aempty'` or `'rotate_Bempty'` or `'rotate_Cempty'` restrict to rotate where the respective "A", "B" or "C" part above is an empty subtree.

`rotate_Aempty` is in the manner of (believe),

A. Bonnin and J.M. Pallo, "A Shortest Path Metric on Unlabelled Binary Trees", Pattern Recognition Letters, volume 13, 1992, pages 411-415.

In terms of balanced binary, the rotate "aaaa" part is empty so triplet 101 -> 110. Flip 01->10 is per "Flip" below, so the result here is edge intersection of `rotate` and `flip`, ie. those edges present in both.

``````    edge from   101       rotate_Aempty
to    110

-------> 110010
/                                  N => 3
101010                     111000      rel_type => "rotate_Aempty"
\                        ^
--> 101100 --> 110100 -/``````

Every 110 substring can be reached from a 101, so the only predecessorless is balanced binary without 110, which is 101010.

Every vertex with a 101 has a successor. This first 1 is a vertex without left but with right. Conversely without 101 is each 10 as 100 or at end of string. That means whenever absent left must also have absent right. This restriction is Motzkin trees so number of successorless

``    successorless = Motzkin(N-1) = 1,1,1,2,4,9,21,51,...  (A001006)``

`rotate_Cempty` is empty C. This is isomorphic to empty A by considering binary trees in mirror image and rotate left edge to right.

In balanced binary, C-empty has 1 after the B subtree, so either 0 or end of string. Identifying places to rotate normally doesn't look at the length of B, but for C-empty must check what is after. For N=3, C-empty is identical to `rotate_last` tree, but bigger C-empty and A-empty are not trees.

``````    edge from 1aaaa0 1bbbb0 [0 or end]     rotate_Cempty
to  11aaaa0 bbbb0``````

`rotate_Bempty` is per Pallo ("Rotational" above) who calls it "central rotate" (and takes "y,B" together requiring them a single vertex).

``````         -------> 110010 -------_
/                        v         N => 3
101010                     111000      rel_type => "rotate_Bempty"
\                        ^
--> 101100     110100 -/``````

In terms of `Lweights`, Pallo notes that B empty means the y vertex is weight 1 (nothing under) and the rotate increases it (when possible, and by smallest amount as usual for a rotate).

In balanced binary, B empty is a 0 after the rotate bit pattern, so rotate at each 010.

``````    edge from    1aaaa0 1 0               rotate_Bempty
to     1 1aaaa0 0
^-- must 0 after``````

The number of edges can be calculated by a recurrence summing over k vertices in the left subtree, n-k-1 in the right, multiplying rotates within the left by number of subtrees right, and vice versa, and new rotate at the root which is right subtree with empty left which is n-k-2. The result is

``````    num edges = binomial(2N-2, N-2)
= 0, 0, 1, 4, 15, 56, 210, 792, ...   (A001791)``````

Graph vertices without successor have nowhere an empty B. This means every tree vertex (y) with a right child also has a left child. This is the Motzkin restriction as per A-empty above. The rotate sends a tree to the corresponding form in mirror image, so vertices without predecessor are likewise. This mirror imaging also means the graph is isomorphic to its own edge reversal (`\$graph->transpose`).

Dexter

Option `rel_type => 'dexter'` is a multi-step block shift of

``````         -------> 110010 -------_
/                        v          N => 3
101010          --------->  111000      rel_type => "dexter"
\          /
--> 101100 --> 110100``````

Chapoton considers shifts (and rotates) going up and left, but here rotate is up and right and dexter here is taken the same. (The difference is whether to read left to right or right to left.) In terms of balanced binary,

``````    from   (0 or start) 1aaaa0 111     one or more following 1s
to                 111 1aaaa0``````

Dexter shift moves one or more of the 1s which are after 1aaaa0. This is one or more rotates at the same place.

The 1aaaa0 is restricted to be preceded by 0 or start of string, it cannot be preceded by 1. This means 1s are taken in a single bite. For example, three 1s are a step but not two 1s then further step remaining 1. When two are taken, the result is "11 1aaaa0 1" and 1aaaa0 is now preceded by a 1 so not eligible for a further shift.

Chapoton notes that all `rotate_rightarm` (see "Rotate Right or Left Arm" above) have the necessary 0 or start, so `rotate_rightarm` edges are a subset of `dexter`. When all the 1s are taken, the result is per `split` (see "Split" below), but split differs in also shifting across multiple blocks and it does not take non-maximal 1s.

In terms of binary trees, the restriction is rotate at an x which is a right child or the root. Multiple 1s are a chain of left edges down from y. The following example is two 1s y,z. The A subtree rotates to under z. Further rotate of 1A0 is disallowed because its 1 is x which is now a left child.

``````      t                     t
/ \     (leftwards)   / \
T   x      ------>    T   y              t   x     yz
/ \                   / \       from  1T0 1 A 0 11 B 0 C 0 D
A   y                 z   D       to       1 11 A 0
/ \               / \
z   D             x   C        x = right child (or root)
/ \               / \
B  C              A   B``````

Successorless graph vertices are no block preceded by 0 and followed by 1. Per Chapoton, the number of these is the Motzkin numbers. The condition in the tree is any right edges must be under left child.

``    successorless = Motzkin(N-1) = 1,1,1,2,4,9,21,51,...  (A001006)``

Predecessors are from each balanced binary 11. This is the 11 of "11aaaa0" in "to" above coming from a shift past the 1aaaa0. That shift is of the first 1, plus all preceding 1s. These 11 locations are the same as for `rotate` (each left edge), but coming from a different vertex when preceding 1s. The total number of edges is same, though dexter is not degree regular the way rotate is.

``````    num edges = same as rotate
= (N-1)/2*Catalan(N) = 0,0,1,5,21,84, ... (A002054)``````

Split

Option `rel_type => 'split'` is graph edge where split of a set of siblings. This is the Kreweras lattice,

G. Kreweras, "Sur les Partitions Non-Croisées d'Un Cycle", Discrete Mathematics, volume 1, number 4, 1972, pages 333-350.

``````          ---> 101100 ---_            N => 3
/                v           rel_type => "split"
101010 --> 110010 --> 111000
\                ^
---> 110100 ---/``````

Kreweras considers the lattice in terms of non-crossing partitions of the integers 1..N. Non-crossing means if sets have overlapping min to max ranges then one must be entirely within a gap between elements of the other, the way children fall between siblings in a pre-order labelled forest. Non-crossing sets are all and only the sets of siblings of ordered forests (with roots reckoned siblings of each other).

Graph edges are where one set in a partition splits into two sets to reach another partition. The set getting the first element remains. The other set is consecutive elements and they split out by dropping to deeper in the forest.

``````      1         8            1        8
|\ \ \    |            |  \     |         pre-order forests
2 3 5 6   9            2    6   9        (post-order similar)
|   |                |\   |
4   7                3 5  7
|
siblings sets           4         split 2,3,5,6
[1,8] [2,3,5,6]                    by dropping 3,5 down
[4,7]                        [2,6] [3,5]``````

The starting vertex is ordered forest all singletons which is 1 set of siblings. A split gives 2 sets, and further split 3 sets, and so on until N sets which is every vertex alone in its set (path-N down).

In balanced binary, split is a block of 1s moving to before one or more preceding balanced substrings.

``````    edge from    1aa0 .. 1aa0 111       across one or more
to     111 1aa0 .. 1aa0        preceding balanceds``````

The block of 1s is maximal, ie. all the 1s following a 0. This is all children moving down (moving only some would change the siblings below). Each 1aa0 is a further preceding sibling moving down with it to form the new sibling set.

The number of edges in the graph can be counted by some recurrences on N vertices, k roots, second root vertex c. 2..c-1 is a sub-forest and c..N is 1 fewer roots. In the balanced binary this is k many blocks with first size c. Multiplying count of splits in one part by number of the other part reaches

``    num edges = binomial(2N,N-2) = 0,1,6,28,120,495, ... (A002694)``

Flip

Option `rel_type => 'flip'` is graph edge for a balanced binary flip 01 -> 10. This is the Stanley lattice, one of various given in

``````    from 101100           /\  -->  /\/\          valley \/
to  110100        /\/  \     /    \         flip up to /\ peak
^^

--> 101100 --_                   N => 3
/              v                  rel_type => "flip"
101010             110100 --> 111000
\              ^
--> 110010 --/``````

In terms of pre-order `Ldepths`, the step is where one entry increases by +1. Such an increase is possible (ie. goes to valid depths) when <= its preceding entry (and first entry depth 0 never increases).

These Ldepth increases mean the lattice is "graded" by total Ldepths (which is area under the mountain range). Ldepths run from start 0,0,0,0 to end 0,1,2,3 so path length start to end is sum of those terms which is triangular number N*(N-1)/2. Stanley leaves it as an exercise to show the number of different such paths (maximal chains) is, adapted to N numbering here,

``````                                 binomial(N,2) !
max chains = --------------------------------------------------
(2N-3) * (2N-5)^2 * (2N-7)^3 * ... * 3^(N-2) * 1^(N-1)

= 1, 1, 1, 2, 16, 768, 292864, ...    (A005118)``````

Filling

Option `rel_type => 'filling'` is graph edges where balanced binary flips pairs 01 -> 10 per

``````    101010 ----_                     N => 3
v                    rel_type => "filling"
101100 --> 110100 --> 111000
^
110010 ----/

edge from   ... 01 ... 01 ... 01 ...     all 01 pairs
to    ... 10 ... 10 ... 10 ...``````

They show the starts (`\$graph->predecessorless_vertices`) are balanced binary decomposable or containing 0011. Decomposable means can be broken into two balanced strings B1,B2, so there is some return to the zero line before the end. In N=3 shown above, starts are just the decomposables. The 0011 rule first applies in N=5 where 1110011000 is not decomposable but is a start because contains 0011.

Each vertex has just one `filling` destination so the result is a tree and ends at 11110000 which is the sole string with no 01s at all.

In terms of `Ldepths`, filling is +1 of all entries which are able to increase, meaning <= preceding entry. The places able to increase are determined before any increasing takes place.

Relation Direction

For a directed graph, edges are in the direction of the rules above. This is the default `rel_direction => 'up'`. Direction "down" is the opposite, the same as `\$graph->transpose`. Direction "both" is edges both ways. An undirected graph is just one edge between vertices in all cases.

For balanced binary, the various rules are a lexicographic (and numeric) increase. The lattices go from global minimum 10101010 up to global maximum 11110000. Or in some relations other minima or maxima too.

`balanced_postorder` does some reversing so that the start becomes 11110000 and the end becomes 10101010. This is because `vertex_name_type` changes only the vertex name, not the object represented nor the relation rule. Direction "down" can be used if desired to put edges the other way. In the case of `rotate`, the rule in `balanced_postorder` and `down` becomes

``````    edge from   0 1aaaa0       vertex_name_type => balanced_postorder
to    1aaaa0 0       rel_direction => down``````

The 0 is a descent. Moving it to after the balanced following has the effect of shifting 1aaaa0 up and left. Various authors prefer this form, for example Bernardi and Bonichon. Balanced coding and rotate move opposite ways, so the choice is which one to prefer as the "bit first".

``````    preorder  coding "1 left 0 right",  rotate "balanced 1"
postorder coding "left 1 right 0",  rotate "0 balanced"``````

The default here is to prefer pre-order and rotate in the direction which is a lex increase of that preorder.

Lattice Refinement

As variously noted above, `split`, `rotate`, and `flip`, all form lattices (partial ordered set algebras). They are successive refinements, meaning two elements comparable in one remain comparable in the next, and some extra comparability added.

``    split --> rotate --> flip      lattice refinement``

In directed graph terms, refinement means at a given vertex the reachable successors (`\$graph->all_successors(\$v)`) expand so everything which was reachable remains so, and possibly more reachable too. The path length to reach something may increase. Reachable predecessors expand in the same way.

In terms of the relation rules on balanced binary, these extensions are simply that a `split` step can be built by one or more `rotate`, and a `rotate` can be built by one or more `flip`.

FUNCTIONS

`\$graph = Graph::Maker->new('Catalans', key => value, ...)`

The key/value parameters are

``````    N            => integer, represented trees size
graph_maker  => subr(key=>value) constructor,
default Graph->new

rel_type     => string
"rotate" (default),
"rotate_first", "rotate_last",
"rotate_Aempty", "rotate_Bempty", "rotate_Cempty",
"rotate_rightarm", "rotate_leftarm"
"dexter"
"split",
"flip", "filling"

rel_direction     => string "up" (default), "down", "both"

vertex_name_type  => string
"balanced" (default), "balanced_postorder"
"Ldepths", "Rdepths_postorder",
"Ldepths_inorder","Rdepths_inorder","Bdepths_inorder",
"Lweights", "Rweights",
"vpar", "vpar_postorder"

comma          => string, default "," or empty ""``````

Other parameters are passed to the constructor, either the `graph_maker` coderef or `Graph->new()`.

If the graph is directed (the default) then edges are only in the "successor" direction for the given `rel_type`.

FORMULAS

The current implementation uses arrays of balanced binary 0,1 internally, being the default preorder `balanced`. The arrays are generated iteratively in the same way as Math::NumSeq::BalancedBinary (see docs there for notes). Some recursion or even some Gray code stepping is possible (and which would be fine since no particular order is needed), but the iteration is simple enough.

A relation type examines and manipulates an array to construct destinations. Conversions are made from the arrays to the chosen `vertex_name_type`. These are one-pass over an array, possibly with a stack remembering pending output or depth. For postorder output in some cases it's helpful to go from end to start (of what is otherwise preorder).

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

``````    all rel_type
1310   N=0 and N=1 singleton
19655  N=2, path-2

rotate
340    N=3, 5-cycle
33547  N=4
33549  N=5
33551  N=6

rotate_rightarm = rotate_leftarm
286    N=3, path-5
33615  N=4
33617  N=5
33619  N=6

rotate_first
286    N=3, path-5
33563  N=4
33565  N=5
33567  N=6

rotate_last
286    N=3, path-5
33569  N=4
33571  N=5
33573  N=6

rotate_Aempty = rotate_Cempty
286    N=3, path-5
33607  N=4
33609  N=5
33611  N=6

rotate_Bempty
286    N=3, path-5
33601  N=4
33603  N=5
33605  N=6

dexter
206    N=3, 4-cycle and leaf
33621  N=4
33623  N=5
33625  N=6

flip
206    N=3, 4-cycle and leaf
33589  N=4
33591  N=5
33593  N=6

filling
544    N=3, star-5
33595  N=4
33597  N=5
33599  N=6

split
264    N=3
33557  N=4
33559  N=5
33561  N=6``````

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

``````    A000108    num vertices, Catalan numbers

rotate
A002054    num edges, (n-1)/2*Catalan
A000260    num intervals
A027686    num paths start to end (lattice maximal chains)

rotate_rightarm = rotate_leftarm
A002057    num edges, 4/(N+2) * binomial(2N-1, N-2)
A009766    row widths, Catalan triangle

rotate_first
A141364    num edges, Catalan-1
A009766    row widths, Catalan triangle

rotate_Bempty
A001791    num edges, binomial(2N-2,N-2)
A001006    num predecessorless, Motzkin numbers
A058987    num predecessorful, Catalan-Motzkin
A001006    num successorful, Motzkin numbers
A058987    num successorless, Catalan-Motzkin

dexter
A002054    num edges, (n-1)/2*Catalan   (same as rotate)
A000257    num intervals

split
A002694    num edges, binomial(2N,N-2)
A001764    num intervals
A000272    num paths start to end (lattice maximal chains)

flip
A002054    num edges, count DU, binomial(2N-1,N-2)
A005700    num intervals
A005118    num paths start to end (lattice maximal chains)

filling
A086581    num predecessorful vertices, N>=2
A071740    num predecessorless vertices, N>=2``````

In the above, "num intervals" means the number of pairs of vertices \$u to \$v where \$v is reachable from \$u. In a lattice this means \$u and \$v are comparable (`\$u <= \$v`). \$u reachable from \$u itself is included (an empty path), so sum `1 + \$graph->all_successors(\$u)` over all \$u.