/ 
Graph-Maker-Other-19
/ Graph::Maker::FibonacciLattice

NAME

Graph::Maker::FibonacciLattice - create Fibonacci lattice graph

SYNOPSIS

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

DESCRIPTION

Graph::Maker::FibonacciLattice creates Graph.pm graphs of the Fibonacci lattice per

Richard P. Stanley, "The Fibonacci Lattice", Fibonacci Quarterly, volume 13, number 3, October 1975. http://fq.math.ca/13-3.html http://fq.math.ca/Scanned/13-3/stanley.pdf

Vertex names are strings of 1s and 2s like 1122121, with sum <= N. Edges are by increasing a 1 to 2, or by appending a 1, thus increasing the sum by +1. The start is an empty string.

[empty] ---> 1 ---> 2 ---> 21            
              \          ^             N => 3
               \       /
                --> 11 --> 12
                      \
                       --> 111

Stanley conceives the lattice as infinite (locally finite in that vertices with given sum are finite). The graph here is vertices with sums 0 to N inclusive.

The number of vertices with sum = k is Fibonacci number F(k+1). That follows by making k from k-1 append 1 or k-2 append 2. (Or equivalently per Stanley, sum over binomials choosing where 1s.)

VK(k) = VK(k-1) + VK(k-2)                  num vertices sum k
          starting VK(0)=1, VK(1)=1
      = Fibonacci(k+1)
      = 1, 1, 2, 3, 5, 8, 13, 21, ...      (A000045)

V(N)   = sum(k=0,N, VK(k))             num vertices
       = Fibonacci(N+3) - 1
       = 1, 2, 4, 7, 12, 20, 33, 54, ...   (A000071)

The number of 1s in the vertices of sum k is a similar recurrence, but an extra 1 in the append to each V(k-1). Count of 2s is Ones(k-1).

Ones(k) = Ones(k-1) + VK(k-1) + Ones(k-2)      total 1s in k
            starting Ones(0)=0, Ones(1)=1
        = 0, 1, 2, 5, 10, 20, 38, 71, ...      (A001629)

Edges leaving k are each such 1 becoming 2, and an append 1 to each vertex. Total graph edges are sum over k

EK(k) = Ones(k) + V(k)                    num edges leaving k
      = 1, 2, 4, 8, 15, 28, 51, 92, ...   (A029907)

E(N)  = sum(k=0,N-1, EK(k)                num edges
      = 0, 1, 3, 7, 15, 30, 58, 109, ...   (A023610)

There are various different paths possible from the empty start up to the sum=N end vertices. The total number is a recurrence

P(N) = P(N-1) + (N-1)*P(N-2)
         starting P(0)=1, P(1)=1
     = 1, 1, 2, 4, 10, 26, 76, 232, ...    (A000085)

Vertices 1xxxx in N descend to empty by first descending the xxxx N-1, then the initial 1 with no extra ways. Vertices 2xxxx in N descend by descending the xxxx of N-2, but with choice of where to decrease 2->1. That can be done before any of the N-2 steps of xxxx, or after them, so N-1. This paths count is OEIS A000085 and has many other combinatorial interpretations.

Edges leaving k are each such 1 becoming 2, and an append 1 to each vertex.

FUNCTIONS

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

The key/value parameters are

N            => integer, for sums 0 to N
graph_maker  => subr(key=>value) constructor,
                 default Graph->new

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.

HOUSE OF GRAPHS

House of Graphs entries for graphs here include,

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

1310     N=0, singleton
19655    N=1, path-2
500      N=2, star-4 claw
33640    N=6 (Stanley's example)

OEIS

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

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

A000071    num vertices, Fibonacci - 1
A023610    num edges
A029907    num edges leaving vertices of sum k
A000085    num maximal paths

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/.