cp's OEIS Frontend

A363893 Number of weakly connected components of an addsub configuration graph with respect to integers mod n over a path with two vertices.

%I A363893 #24 Sep 27 2023 15:52:39
%S A363893 1,2,1,4,2,3,1,5,4,4,2,6,3,11,1,11,5,6,4,12,4,7,2,13,6,14,3,10,11,25,
%T A363893 1,29,11,18,5,12,6,21,4,25,12,34,4,32,7,13,2,17,13,48,6,16,14,25,3,47,
%U A363893 10,16,11,18,25,87,1,95,29,18,11,32,18,19,5
%N A363893 Number of weakly connected components of an addsub configuration graph with respect to integers mod n over a path with two vertices.
%C A363893 The addsub game is played on a path with two vertices {u,v}. We define a configuration of the integers mod n on {u,v} by assigning weights wt(u) and wt(v).
%C A363893 An addsub move from u to v is a reassignment of weights given by wt(u) -> wt(u) - wt(v) (mod n) and wt(v) -> wt(u) + wt(v) (mod n). An addsub move from v to u is defined analogously.
%C A363893 The addsub configuration graph with respect to the integers mod n over {u,v} is the directed graph in which each node corresponds to a configuration (wt(u),wt(v)) and a directed edge from a configuration to the resulting configuration is attainable via a single addsub move.
%D A363893 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, CRC Press, 2001.
%H A363893 E. Fiorini, M. Lind, A. Woldar, and T. W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Wong/wong31.html">Characterizing Winning Positions in the Impartial Two-player Pebbling Game on Complete Graphs</a>, Journal of Integer Sequences, 24(6) (2021).
%H A363893 E. Fiorini, M. Lind, and A. Woldar, <a href="https://doi.org/10.1007/s00373-021-02453-z">On Properties of Pebble Assignment Graphs</a>, Graphs and Combinatorics, 38(2) (2022), 45.
%H A363893 E. Fiorini, G. Johnston, M. Lind, A. Woldar, and T. W. H. Wong, <a href="https://doi.org/10.1007/s00373-022-02552-5">Cycles and Girth in Pebble Assignment Graphs</a>, Graphs and Combinatorics, 38(5) (2022), 154.
%e A363893 For n=3, the (u,v) sequence of addsub moves forms the directed cycle (0,1)->(2,1)->(1,0)->(1,1)->(0,2)->(1,2)->(2,0)->(2,2)->(0,1). The (v,u) sequence of addsub moves forms the directed cycle (0,1)->(1,1)->(2,0)->(2,1)->(0,2)->(2,2)->(1,0)->(1,2)->(0,1). These two directed cycles form one weakly connected component. The isolated vertex (0,0) is a loop and forms the second weakly connected component. Therefore, a(3)=2.
%t A363893 Upto=25;
%t A363893 Table[
%t A363893   VertexSet:={};
%t A363893   EdgeSet:={};
%t A363893   (* Compute configuration graph for integers mod n *)
%t A363893   Do[
%t A363893     Do[AppendTo[VertexSet,{i,j}];
%t A363893       AppendTo[EdgeSet,{i,j}\[DirectedEdge]{Mod[i-j,n],Mod[i+j,n]}];
%t A363893       AppendTo[EdgeSet,{i,j}\[DirectedEdge]{Mod[j+i,n],Mod[j-i,n]}],
%t A363893       {j,0,n-1}],
%t A363893     {i,0,n-1}];
%t A363893   (* Print n-th term *)
%t A363893   Length[WeaklyConnectedComponents[Graph[VertexSet,EdgeSet]]],
%t A363893   {n,2,Upto}]
%Y A363893 Cf. A340631, A346197, A346401.
%K A363893 nonn
%O A363893 2,2
%A A363893 _Patrick G. Cesarz_, _Eugene Fiorini_, _Charles Gong_, _Kyle A. Kelley_, _Philip Thomas_, and _Andrew Woldar_, Jun 26 2023