A378004 Number of winning positions of Gordon Hamilton's Jumping Frogs game with n single frogs, up to left-right symmetry.

1, 1, 2, 5, 12, 39, 123, 412, 1431, 4831, 17363, 60697, 219777, 781260, 2858031, 10329091, 38103069, 138996792

Offset

1,3

Comments

For the rules of the Jumping Frogs game, see A377232.

Counts the number of distinct winning positions of the game with exactly n frogs, each in a different place. Positions are considered the same if one can be obtained from the other by reversing it left-to-right.

Equivalently, a(n) is the number of unordered pairs {k, A030101(k)} with k odd such that the binary weight A000120(k) = n, and k occurs in A377232.

Since a stack of k frogs moves exactly k spaces in the Jumping Frogs game, the sum of the lengths of all moves starting from a position with n single frogs is at most A000217(n-1), the (n-1)st triangular number. Hence if it is a winning position, the length of the position (excluding unoccupied places to the left of the first occupied one, and unoccupied places to the right of the last occupied one) is at most one more than this triangular number. Therefore a(n) is finite for all n.

References

See references at A377232.

Links

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

Jinyuan Wang, Python program.

Example

For four frogs, we can win:
  1111 -> 0211 -> 0013 -> 0004
  11101 -> 02101 -> 03001 -> 00004
  11011 -> 02011 -> 02020 -> 04000
  111001 -> 201001 -> 003001 -> 000004
  1101001 -> 0201001 -> 0003001 -> 0000004
Any other position with four frogs in different places is either a left-right reversal of one of these, or no sequence of moves will result in all frogs in the same place. Hence a(4)=5.
Equivalently, one can start with four frogs in a single place and make a tree of all possible reverse moves, and then count leaves in which all frogs are in different places:
                       _____________4____
                      /             |    \
                 ___3001___        202    13
                /   |  |   \      /   \    |
          201001 12001 2101 1021 1102 112 121
         /   |     |         |    |
  1101001 111001 11101      1111 11011
Again we see that a(4) = 5. (Note that nodes whose labels or reversed labels have already occurred earlier in a row are omitted from this tree.)

Crossrefs

Cf. A000120, A000217, A030101, A377232, A377307.

Sequence in context: A050237 A050258 A051436 * A054581 A203151 A140440

Adjacent sequences: A378001 A378002 A378003 * A378005 A378006 A378007

Keyword

nonn,more

Author

Glen Whitney, Nov 13 2024

Extensions

a(16)-a(18) from Jinyuan Wang, Nov 25 2024

Status

approved