view release on metacpan or  search on metacpan

lib/Graph/Maker/Catalans.pm  view on Meta::CPAN

vertex names.  The default is empty "" for balanced binary or "," comma for
the others.

Terms are single digits for weights or vpar of N E<lt> 10, and depths of N
E<lt>= 10.  Omitting the comma by C<comma =E<gt> ''> is then unambiguous and
might be preferred for compact viewing.  Ambiguity at N=10 would be
Catalan(10) = 16796 vertices which is big but possible.

=cut

# GP-DEFINE  Catalan_number(n) = binomial(n<<1,n) / (n+1);
# GP-Test  Catalan_number(10) == 16796

=pod

=head2 Rotate

The default C<rel_type =E<gt> 'rotate'> is the X<Tamari lattice>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
X<associahedron>associahedron.

=over

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

=back

         -------> 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, so each tree edge gives a graph edge and 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)

=cut

# GP-DEFINE  RotateNumEdges_formula(N) = (N-1)/2*Catalan_number(N);
# GP-DEFINE  RotateNumEdges(N) = if(N==0,0, RotateNumEdges_formula(N));
# GP-Test  vector(6,N,N--; RotateNumEdges(N)) == [0,0,1,5,21,84]
# GP-Test  vector(20,N,N--; RotateNumEdges(N)) == \
# GP-Test  vector(20,N,N--; binomial(2*N-1,N-2))
# GP-Test  RotateNumEdges_formula(0) == -1/2

=pod

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 can rotate per the "from" form above, so number of successors is
number of 01 pairs.  Each 11 in the "to" form 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 and its subtree drop down to
become the first child of y.  y's other children B remain.

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

In terms of C<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 vertex sequence is unchanged.  Pallo
reaches the same as Tamari that this operation forms a lattice.

=over

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

=back

Taking C<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.  Geyer draws N=4 and N=5 in this
style.  N=5 or more, in 2D projection at least, tends to become too busy to
see much.

=cut

# Winfried Geyer, "On Tamari Lattices", Discrete Mathematics, volume 133,
# 1994, pages 99-122.
# 82586438.pdf
# 

=pod