/ 
Graph-Maker-Other-19
/ Graph::Maker::CatalansUpto

NAME

Graph::Maker::CatalansUpto - create graphs of Catalan object growth

SYNOPSIS

use Graph::Maker::CatalansUpto;
$graph = Graph::Maker->new ('Catalans_upto', N => 4);

DESCRIPTION

Graph::Maker::CatalansUpto creates Graph.pm graphs where each vertex represents a "Catalan object". See Graph::Maker::Catalans for description and for vertex_name_type options. The number of vertices is sum Catalan numbers

num vertices = sum k=0 to N of Catalan(k)
             = 1, 2, 4, 9, 23, 65, ...   (A014137)

Edges are where a Catalan object grows to a bigger such object under some rule.

Below

Option rel_type => 'below' is graph edge extending a binary tree by adding a new vertex below, at an otherwise empty child position. Stanley considers this as lattice of order ideals of a complete binary tree.

Richard P. Stanley, "The Fibonacci Lattice", Fibonacci Quarterly, volume 13, number 3, October 1975, pages 215-232, lattice A2 = J(T2) page 224. https://fq.math.ca/13-3.html, https://fq.math.ca/Scanned/13-3/stanley.pdf

In terms of balanced binary, adding below is to insert 10 before 0 or at end of string.

from     (0 or end-of string)
 to   10 (0 or end-of string)

                     ----> 101010
                    /  --> 101100
                   |  /
              /--> 1010---v             N => 3
[empty] --> 10             110010       rel_type => "below"
              \--> 1100---^
                   |  \
                    \  --> 110100
                     ----> 111000

Each length 2k string has k 0s plus the end so k+1 successors each vertex.

num edges = sum k=0 to N-1 of (k+1)*Catalan(k)
          = 0, 1, 3, 9, 29, 99, ...    (A006134)

The number of paths from start up to a successorless end is choice k+1 at each vertex so paths = 1*2*...*N = N!.

FUNCTIONS

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

The key/value parameters are

N            => integer, trees sizes 0 to N inclusive
graph_maker  => subr(key=>value) constructor,
                 default Graph->new

rel_type     => string
  "below" (default)

rel_direction     => string  \
comma             => string  | see Graph::Maker::Catalans
vertex_name_type  => string  /

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.

HOUSE OF GRAPHS

House of Graphs entries for graphs here include

https://hog.grinvin.org/ViewGraphInfo.action?id=1310 etc

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

below
  340    N=2, star-4, claw

OEIS

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

http://oeis.org/A000108 (etc)

A014137    num vertices, cumulative Catalan numbers
A000108    row widths, Catalan numbers

below
  A006134    num edges
  A000142    num paths start to successorless, N!

SEE ALSO

Graph::Maker

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2018, 2019, 2020, 2021 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.