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

0, 0, 0, 0, 1, 2, 5, 7, 10, 13, 18, 22, 29, 34, 42, 49, 60, 69, 86, 100, 121, 139, 164, 187, 219, 252, 296, 343, 400, 458, 532, 605, 696, 794, 917, 1050, 1214, 1389, 1599, 1823, 2087, 2371, 2710, 3080, 3521

Offset

1,6

Comments

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.

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.

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

References

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

Links

Table of n, a(n) for n=1..45.

R. A. Beeler and A. D. Gray, An Introduction to Peg Duotaire on Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 104, 2018, pp. 171-186.

Nathan Hurtig, SageMath program to compute values

Formula

a(n) <= A000094(n).

Example

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.
   1-1-1-1-1
       |
   1-0-1-1-1
       |     (move is forced)
   1-1-0-0-1
       |
   0-0-1-0-1 (no moves remain)

Crossrefs

Cf. A000094.

Sequence in context: A189757 A094065 A073593 * A241510 A088947 A288209

Adjacent sequences: A364448 A364449 A364450 * A364452 A364453 A364454

Keyword

nonn

Author

Michael Carrion, Nathan Hurtig, Maggie X. Lai, Sarah Lohrey, Brittany Ohlinger, Jul 25 2023

Status

approved