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 selfloop at this partition so all vertices have outdegree 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.
Nontriangular 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
Ethan Akin and Morton Davis, "Bulgarian Solitaire", American Mathematical Monthly, volume 92, number 4, April 1985, pages 237250. http://www.jstor.org/stable/2323643
num components = num compositions of t,r up to cyclic shifts,
for N = triangular(t1) + 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. indegree 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^(N1), 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^(N1)  Fibonacci(N+1).
Brian Hopkins, Michael A. Jones, "ShiftInduced 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 selfloop at the fixed point of triangular N.Other parameters are passed to the constructor, either
graph_maker
coderef orGraph>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 2cycle 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 2cycle which as simple undirected is a 2path. N=8 includes such a 2cycle collapsing too.
1310 N=1, singleton
19655 N=2, path2
32234 N=3, path3
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, path4
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
http://oeis.org/A000041 (etc)
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 (nonrepeating)
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^(N1) or 1 when N=0
A000045 num with predecessors = Fibonacci(N+1)
A008466 num predecessorless, Garden of Eden
= 2^(N1)  Fibonacci(N+1)
SEE ALSO
LICENSE
Copyright 2018, 2019 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/.