login
A364451
a(n) is the number of trees of diameter 4 with n vertices that are N-games in peg duotaire.
1
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
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.
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
KEYWORD
nonn
STATUS
approved