Graph::Maker::BulgarianSolitaire - create Bulgarian solitaire trees and graphs
use Graph::Maker::BulgarianSolitaire; $graph = Graph::Maker->new ('Bulgarian_solitaire', N => 6);
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
Ethan Akin and Morton Davis, "Bulgarian Solitaire", American Mathematical Monthly, volume 92, number 4, April 1985, pages 237-250. http://www.jstor.org/stable/2323643
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
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 => $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.
$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
compositionsdefaults to "0" meaning not compositions, but partitions.
no_self_loopomits the self-loop at the fixed point of triangular N.
Other parameters are passed to the constructor, either
If the graph is directed (the default) then edges are added just in the successor direction. Option
undirected => 1creates 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 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
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)
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)
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/.