/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::BulgarianSolitaire

NAME

Graph::Maker::BulgarianSolitaire - create Bulgarian solitaire trees and graphs

SYNOPSIS

use Graph::Maker::BulgarianSolitaire;
$graph = Graph::Maker->new ('Bulgarian_solitaire', N => 6);

DESCRIPTION

Graph::Maker::BulgarianSolitaire creates Graph.pm graphs of Bulgarian solitaire steps.

             +-+
             v |     (self loop)
            1,2,3
              ^
              |
             2,4                    N => 6
           ^     ^                has 11 vertices
          /       \
    1,1,1,3        1,5
     /            /    \
 2,2,2           6    1,1,1,1,2
   |             |
  3,3       1,1,1,1,1,1
   |
 1,1,4
   |
1,1,2,2

Each vertex is a partition of the integer N, meaning a set of integers which sum to N. Vertex names are the terms in ascending order separated by commas. For example vertex 1,3,3,5 in N=12.

num vertices = 1, 1, 2, 3, 5, 7, 11, 15, ...   (A000041)
num edges = num vertices (one out each)

Bulgarian solitaire steps a partition by subtracting 1 from each element, summing the subtractions as a new term, and discarding any zeros. For example 1,3,3,5 steps to 2,2,4,5. Graph edges are from a partition to its successor by this rule.

N=0 is a single empty partition. N=1 is a single 1 partition.

If N is a triangular number N = t*(t+1)/2 = 1,3,6,10,... then partition 1,2,3,...,t steps to itself, so is a "fixed point". Per various authors, all partitions in triangular N eventually reach this fixed point (because the diagonal extent eventually decreases). The default is to include a self-loop at this partition so all vertices have out-degree 1. Optional parameter no_self_loop can omit,

$graph = Graph::Maker->new ('Bulgarian_solitaire', N => 10,
                            no_self_loop => 1);

no_self_loop is intended for making such N a tree, rather than tree and loop.

Non-triangular N gives one or more components, each with a cycle at the top. The number of components ($graph->connected_components()), is determined, for all N, in

num components = num compositions of t,r up to cyclic shifts,
                   for N = triangular(t-1) + r
            = 1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,3,4,3 ... (A037306)

Some cycles are between 2 vertices. In an undirected simple graph, they become a single edge between the two. A multiedged=>1 or countedged=>1 has two edges between them.

Some vertices have no predecessors, ie. in-degree 0 ($graph->predecessorless_vertices()). These are called "Garden of Eden" partitions after some terminology of Edward Moore in cellular automata. They are characterized and counted in

    Brian Hopkins and James A. Sellers, "Exact Enumeration of Garden of Eden Partitions", INTEGERS: Electronic Journal of Combinatorial Number Theory, volume 7 number 2, 2007, #A19.

num predecessorless   = 0,0,0,1,1,2,3,5,7,10,14, ... (A123975)
  = sum(j=1,up, (-1)^(j+1) * NumPartions(n - 3*j*(j+1)/2))
num with predecessors = 1,1,2,2,4,5,8,10,15,20,28,... (A260894)

Predecessorless are all partitions with rank <= -2, where rank = LargestTerm - NumTerms (per Dyson). For example largest term 3 and having 5 or more terms is Garden of Eden.

Compositions

Option compositions => $type applies the solitaire rule to compositions of N (partitions with ordered terms). Griggs and Ho call this "Carolina solitaire". $type can be "append" to append the new term or "prepend" to prepend. Append and prepend give the same structure, just with terms in each composition reversed.

1,2,1 ---> 1,3  ---->  2,2 <--- 3,1 <-- 4 <-- 1,1,1,1
          ^   ^       /
         /     \     v                N => 4
     2,1,1      1,1,2          compositions => 'append'

The number of compositions is

num vertices = 2^(N-1), or 1 if N=0 = 1,1,2,4,8,16,... (A011782)
num edges = num vertices (one out each)

Hopkins and Jones show the number of Garden of Eden compositions is 2^(N-1) - Fibonacci(N+1).

    Brian Hopkins, Michael A. Jones, "Shift-Induced Dynamical Systems on Partitions and Compositions", The Electronic Journal of Combinatorics 13 (2006), #R80.

FUNCTIONS

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

The key/value parameters are

N             => integer, to partition
compositions  => string "0", "append", "prepend"
                   default "0"
no_self_loop  => boolean, default false
graph_maker   => subr(key=>value) constructor, default Graph->new

compositions defaults to "0" meaning not compositions, but partitions. no_self_loop omits the self-loop at the fixed point of triangular N.

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

If the graph is directed (the default) then edges are added just in the successor direction. Option undirected => 1 creates an undirected graph. Some steps can be a 2-cycle A->B and back B->A. In an undirected multigraph they are two edges.

HOUSE OF GRAPHS

House of Graphs entries for graphs here include the following. House of Graphs is undirected simple graphs, so for example N=2 is a directed 2-cycle which as simple undirected is a 2-path. N=8 includes such a 2-cycle collapsing too.

1310    N=1, singleton
19655   N=2, path-2
32234   N=3, path-3
330     N=4
820     N=5
32254   N=6
32380   N=7
32256   N=8
32382   N=9
32258   N=10
32384   N=11
32386   N=12
32388   N=13
32390   N=14
32260   N=15
32392   N=16

Compositions are the same as partitions for N<=2, and then

594     N=3, path-4

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

A000041    num vertices = num partitions
             = num edges too
A260894    num with predecessors
A123975    num predecessorless, Garden of Eden
A037306    num connected components
A054531    smallest cycle length = girth, for N>=1
A277227      same, for N>=0
A183110    longest cycle length 
A201144    longest path length (non-repeating)

For N=triangular (so a tree),

A066655    num vertices = num partitions of triangular
             = num edges too
A002378    tree height (pronic numbers)

Compositions,

A011782    num vertices = 2^(N-1) or 1 when N=0
A000045    num with predecessors = Fibonacci(N+1)
A008466    num predecessorless, Garden of Eden
             = 2^(N-1) - Fibonacci(N+1)

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