A364451 - OEIS

%I #14 Aug 05 2023 23:52:32

%S 0,0,0,0,1,2,5,7,10,13,18,22,29,34,42,49,60,69,86,100,121,139,164,187,

%T 219,252,296,343,400,458,532,605,696,794,917,1050,1214,1389,1599,1823,

%U 2087,2371,2710,3080,3521

%N a(n) is the number of trees of diameter 4 with n vertices that are N-games in peg duotaire.

%C Peg duotaire is an impartial normal-play two-player game played on a simple graph, in which each vertex starts with a peg in it. If all vertices have a peg (i.e. the first turn), a move consists of removing some peg from a vertex.

%C If some vertex does not have a peg, then a move hops one peg over another, landing in an adjacent hole and removing the jumped peg. Formally, it is three vertices x, y, z where x, y are adjacent and y, z are adjacent, and x, y have pegs and z does not. After the move, x, y do not have pegs and z does.

%C Note than this sequence is always less than or equal to the number of trees of diameter 4 with n vertices, see A000094.

%D E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays. Vol. 1, CRC Press, 2001.

%H R. A. Beeler and A. D. Gray, <a href="https://www.researchgate.net/publication/324503822_An_Introduction_to_Peg_Duotaire_on_Graphs">An Introduction to Peg Duotaire on Graphs</a>, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 104, 2018, pp. 171-186.

%H Nathan Hurtig, <a href="/A364451/a364451.sage.txt">SageMath program to compute values</a>

%F a(n) <= A000094(n).

%e There is only one tree of diameter 4 with 5 vertices. It is an N-game, as evidenced by the below winning strategy for the first player. We use 1 to represent a vertex with a peg and 0 otherwise.

%e    1-1-1-1-1

%e        |

%e    1-0-1-1-1

%e        |     (move is forced)

%e    1-1-0-0-1

%e        |

%e    0-0-1-0-1 (no moves remain)

%Y Cf. A000094.

%K nonn

%O 1,6

%A _Michael Carrion_, _Nathan Hurtig_, _Maggie X. Lai_, _Sarah Lohrey_, _Brittany Ohlinger_, Jul 25 2023