view release on metacpan or  search on metacpan

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

              = 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

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 C<rotate_...> relation types below restrict to just some rotates
so are edge subsets of full C<rotate>.

=cut

# Knuth volume 4 section 7.2.1.6 exercise 27
# (L<http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz>) considers the
# lattice in ordered forests form, by depths or pre-order sizes.
# With rotate as smallest increase in preorder sizes ...
#
# =over
#
# Joan Lucas, "The Rotation Graph of Binary Trees Is Hamiltonian",
# Journal of Algorithms, volume 9, 1988, pages 503-535.
#
# =back
#
# and simplified
#
# =over
#
# Joan Lucas, Dominique Roelants van Baronaigien, Frank Ruskey, "On Rotations
# and the Generation of Binary Trees", Journal of Algorithms, volume 15, 1993,
# pages 343-366.
# L<http://webhome.cs.uvic.ca/~ruskey/Publications/Rotation/Rotation.html>
#
# =back
#
# The latter approach is to take a Hamiltonian path in N-1 and at each element
# run the new term N alternately up and down in the weights vector, which is
# the N-1 roots under or not under the new vertex N.  They use this to iterate
# through weights vectors one rotation at a time.  Knuth volume 4 section
# 7.2.1.6 algorithm L adapts to binary tree form.
#
# The graph has a Hamiltonian cycle per
#
# =over
#
# Ro-Yu Wu, Hung Lung Wang, "A Simple Proof for the Hamiltonian Property on
# Rotation Grpahs of Binary Trees" The 27th Workshop on Combinatorial
# Mathematics and Computation Theory
#
# =back
#