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.
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
KEYWORD
nonn
AUTHOR
STATUS
approved